Skip to main content
Logo image

Discrete Mathematics: An Open Introduction, 3rd edition

Oscar Levin

Section 2.6 Chapter Summary

Investigate!
Each day your supply of magic chocolate covered espresso beans doubles (each one splits in half), but then you eat 5 of them. You have 10 at the start of day 0.
  1. Write out the first few terms of the sequence. Then give a recursive definition for the sequence and explain how you know it is correct.
  2. Prove, using induction, that the last digit of the number of beans you have on the \(n\)th day is always a 5 for all \(n \ge 1\text{.}\)
  3. Find a closed formula for the \(n\)th term of the sequence and prove it is correct by induction.
In this chapter we explored sequences and mathematical induction. At first these might not seem entirely related, but there is a link: recursive reasoning. When we have many cases (maybe infinitely many), it is often easier to describe a particular case by saying how it relates to other cases, instead of describing it absolutely. For sequences, we can describe the \(n\)th term in the sequence by saying how it is related to the previous term. When showing a statement involving the variable \(n\) is true for all values of \(n\text{,}\) we can describe why the case for \(n = k\) is true on the basis of why the case for \(n = k-1\) is true.
While thinking of problems recursively is often easier than thinking of them absolutely (at least after you get used to thinking in this way), our ultimate goal is to move beyond this recursive description. For sequences, we want to find closed formulas for the \(n\)th term of the sequence. For proofs, we want to know the statement is actually true for a particular \(n\) (not only under the assumption that the statement is true for the previous value of \(n\)). In this chapter we saw some methods for moving from recursive descriptions to absolute descriptions.
  • If the terms of a sequence increase by a constant difference or constant ratio (these are both recursive descriptions), then the sequences are arithmetic or geometric, respectively, and we have closed formulas for each of these based on the initial terms and common difference or ratio.
  • If the terms of a sequence increase at a polynomial rate (that is, if the differences between terms form a sequence with a polynomial closed formula), then the sequence is itself given by a polynomial closed formula (of degree one more than the sequence of differences).
  • If the terms of a sequence increase at an exponential rate, then we expect the closed formula for the sequence to be exponential. These sequences often have relatively nice recursive formulas, and the characteristic root technique allows us to find the closed formula for these sequences.
  • If we want to prove that a statement is true for all values of \(n\) (greater than some first small value), and we can describe why the statement being true for \(n = k\) implies the statement is true for \(n = k+1\text{,}\) then the principle of mathematical induction gives us that the statement is true for all values of \(n\) (greater than the base case).
Throughout the chapter we tried to understand why these facts listed above are true. In part, that is what proofs, by induction or not, attempt to accomplish: they explain why mathematical truths are in fact truths. As we develop our ability to reason about mathematics, it is a good idea to make sure that the methods of our reasoning are sound. The branch of mathematics that deals with deciding whether reasoning is good or not is mathematical logic, the subject of the next chapter.

Exercises Chapter Review

1.

Find \(9 + 16 + 23+ \cdots + 1955\text{.}\)
Solution.
\(\frac{1964\cdot 278}{2} = {272996}\text{.}\)

2.

Consider the sequence \(1, 13, 25, 37, \ldots, 12n + 1\text{.}\)
  1. How many terms are there in the sequence?
  2. What is the second-to-last term?
  3. Find the sum of all the terms in the sequence.
Solution.
  1. \({n-0}\) terms.
  2. \(\displaystyle {12n+\left(-11\right)}\text{.}\)
  3. \(\displaystyle \frac{(12n+2)*({n-0})}{2}\text{.}\)

3.

Consider the sequence given by \(a_n = 2\cdot 5^{n-1}\text{.}\)
  1. Find the first 4 terms of the sequence.
    \(a_1 =\) , \(a_2 =\) , \(a_3 =\) , \(a_4 =\) ,...
    What sort of sequence is this?
    • arithmetic
    • geometric
    • neither
  2. Find the sum of the first 34 terms. That is, compute \(\sum_{k=1}^{34}a_k\text{.}\)
Solution.
  1. \(2, 10, 50, 250, \ldots\) The sequence is geometric.
  2. \(\displaystyle \frac{2\cdot5^{34}-2}{4}={2.91038\times 10^{23}}\text{.}\)

4.

Consider the sequence \(5, 11, 19, 29, 41, 55,\ldots\text{.}\) Assume \(a_1 = 5\text{.}\)
  1. Find a closed formula for \(a_n\text{,}\) the \(n\)th term of the sequence, by writing each term as a sum of a sequence. Hint: first find \(a_0\text{,}\) but ignore it when collapsing the sum.
  2. Find a closed formula again, this time using either polynomial fitting or the characteristic root technique (whichever is appropriate). Show your work.
  3. Find a closed formula once again, this time by recognizing the sequence as a modification to some well known sequence(s). Explain.

5.

Use polynomial fitting to find the formula for the \(n\)th term of the sequence \((a_n)_{n \ge 1}\) which starts,
\begin{equation*} {8, 17, 28, 41, 56}, \ldots \end{equation*}
Note the first term above is \(a_1\text{,}\) not \(a_0\text{.}\)
\(a_n =\)
Solution.
\(a_n = {n^{2}+6n+1}\text{.}\) Here we know that we are looking for a quadratic because the second differences are constant. So \(a_n = an^2 + bn + c\text{.}\) We can work backwards to find that \(a_0 = {1}\text{,}\) so we know \(c= {1}\text{.}\) Then solve the system,
\begin{equation*} \begin{aligned} {8} \amp = a + b + {1}\\ {17} \amp = 4a + 2b + {1} \end{aligned} \end{equation*}
to find \(a = {1}\) and \(b = {6}\text{.}\)

6.

Suppose the closed formula for a particular sequence is a degree 3 polynomial. What can you say about the closed formula for:
  1. The sequence of partial sums.
  2. The sequence of second differences.
Solution.
  1. The sequence of partial sums will be a degree 4 polynomial (its sequence of differences will be the original sequence).
  2. The sequence of second differences will be a degree 1 polynomial - an arithmetic sequence.

7.

Consider the sequence given recursively by \(a_1 = 4\text{,}\) \(a_2 = 6\) and \(a_n = a_{n-1} + a_{n-2}\text{.}\)
  1. Write out the first 6 terms of the sequence.
  2. Could the closed formula for \(a_n\) be a polynomial? Explain.
Solution.
  1. \(4, 6, 10, 16, 26, 42, \ldots\text{.}\)
  2. No, taking differences gives the original sequence back, so the differences will never be constant.

8.

The sequence \((a_n)_{n \ge 1}\) starts \(-1, 0, 2, 5, 9, 14\ldots\) and has closed formula \(a_n = \dfrac{(n+1)(n-2)}{2}\text{.}\) Use this fact to find a closed formula for the sequence \((b_n)_{n \ge 1}\) which starts \(4, 10, 18, 28, 40, \ldots\text{.}\)
Solution.
\(b_n = (n+3)n\text{.}\)

9.

The in song The Twelve Days of Christmas, my true love gave to me first 1 gift, then 2 gifts and 1 gift, then 3 gifts, 2 gifts and 1 gift, and so on. How many gifts did my true love give me all together during the twelve days?

10.

Consider the recurrence relation \(a_n = 5a_{n-1} + 14a_{n-2}\) with first two terms \(a_0 = 10\) and \(a_1 = 12\text{.}\)
  1. Write out the first 5 terms of the sequence defined by this recurrence relation.
    \(a_2 =\) , \(a_3 =\) , \(a_4 =\) , ...
  2. Solve the recurrence relation. That is, find a closed formula for \(a_n\text{.}\)
\(a_n =\)
Solution.
The sequence is \(10, 12, {200}, {1168}, {8640}, \ldots\text{.}\) It has closed formula \(a_n = {\left({\frac{58}{9}}\right)\!\left(-2\right)^{n}+\left({\frac{32}{9}}\right)\cdot 7^{n}}\text{,}\) using the characteristic root technique.

11.

Consider the recurrence relation \(a_n = -2a_{n-1} + 8a_{n-2}\) with first two terms \(a_0 = 1\) and \(a_1 = 2\text{.}\)
  1. Find the next two terms of the sequence (\(a_2\) and \(a_3\)):
    \(a_2 =\)
    \(a_3 =\)
  2. Solve the recurrence relation. That is, find a closed formula for \(a_n\text{.}\)
    \(a_n =\)
Solution.
The sequence is \(1, 2, {4}, {8}, {16}, \ldots\text{.}\) It has closed formula \(a_n = {2^{n}}\text{,}\) using the characteristic root technique.

12.

Your magic chocolate bunnies reproduce like rabbits: every large bunny produces 2 new mini bunnies each day, and each day every mini bunny born the previous day grows into a large bunny. Assume you start with 2 mini bunnies and no bunny ever dies (or gets eaten).
  1. Write out the first few terms of the sequence.
  2. Give a recursive definition of the sequence and explain why it is correct.
  3. Find a closed formula for the \(n\)th term of the sequence.
Solution.
  1. On the first day, your 2 mini bunnies become 2 large bunnies. On day 2, your two large bunnies produce 4 mini bunnies. On day 3, you have 4 mini bunnies (produced by your 2 large bunnies) plus 6 large bunnies (your original 2 plus the 4 newly matured bunnies). On day 4, you will have \(12\) mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is \(2, 2, 6, 10, 22, 42\ldots\) starting with \(a_0 = 2\) and \(a_1 = 2\text{.}\)
  2. \(a_n = a_{n-1} + 2a_{n-2}\text{.}\) This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each).
  3. Using the characteristic root technique, we find \(a_n = a2^n + b(-1)^n\text{,}\) and we can find \(a\) and \(b\) to give \(a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}\)

13.

Consider the sequence of partial sums of squares of Fibonacci numbers: \(F_1^2\text{,}\) \(F_1^2 + F_2^2\text{,}\) \(F_1^2 + F_2^2 + F_3^2, \ldots\text{.}\) The sequences starts \(1, 2, 6, 15, 40,\ldots\)
  1. Guess a formula for the \(n\)th partial sum, in terms of Fibonacci numbers. Hint: write each term as a product.
  2. Prove your formula is correct by mathematical induction.
  3. Explain what this problem has to do with the following picture:

14.

Prove the following statements by mathematical induction:
  1. \(n! \lt n^n\) for \(n \ge 2\)
  2. \(\d\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} +\frac{1}{3\cdot 4}+\cdots + \frac{1}{n\cdot(n+1)} = \d\frac{n}{n+1}\) for all \(n \in \Z^+\text{.}\)
  3. \(4^n - 1\) is a multiple of 3 for all \(n \in \N\text{.}\)
  4. The greatest amount of postage you cannot make exactly using 4 and 9 cent stamps is 23 cents.
  5. Every even number squared is divisible by 4.
Hint.
  1. Hint: \((n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}\)
  2. Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions.
  3. Hint: Write \(4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\)
  4. Hint: one 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps.
  5. Careful to actually use induction here. The base case: \(2^2 = 4\text{.}\) The inductive case: assume \((2n)^2\) is divisible by 4 and consider \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) This is divisible by 4 because \(4n +4\) clearly is, and by our inductive hypothesis, so is \((2n)^2\text{.}\)

15.

Prove \(1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2\) holds for all \(n \ge 1\text{,}\) by mathematical induction.
Hint.
This is a straight forward induction proof. Note you will need to simplify \(\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\) and get \(\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\)

16.

Suppose \(a_0 = 1\text{,}\) \(a_1 = 1\) and \(a_n = 3a_{n-1} - 2a_{n-1}\text{.}\) Prove, using strong induction, that \(a_n = 1\) for all \(n\text{.}\)
Hint.
There are two base cases \(P(0)\) and \(P(1)\text{.}\) Then, for the inductive case, assume \(P(k)\) is true for all \(k \lt n\text{.}\) This allows you to assume \(a_{n-1} = 1\) and \(a_{n-2} = 1\text{.}\) Apply the recurrence relation.

17.

Prove using induction that every set containing \(n\) elements has \(2^n\) different subsets for any \(n \ge 1\text{.}\)
Solution.
Let \(P(n)\) be the statement, “every set containing \(n\) elements has \(2^n\) different subsets.” We will show \(P(n)\) is true for all \(n \ge 1\text{.}\) Base case: Any set with 1 element \(\{a\}\) has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is \(2= 2^1\text{.}\) Thus \(P(1)\) is true. Inductive case: Suppose \(P(k)\) is true for some arbitrary \(k \ge 1\text{.}\) Thus every set containing exactly \(k\) elements has \(2^k\) different subsets. Now consider a set containing \(k+1\) elements: \(A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}\) Any subset of \(A\) must either contain \(a_{k+1}\) or not. In other words, a subset of \(A\) is just a subset of \(\{a_1, a_2,\ldots, a_k\}\) with or without \(a_{k+1}\text{.}\) Thus there are \(2^k\) subsets of \(A\) which contain \(a_{k+1}\) and another \(2^{k+1}\) subsets of \(A\) which do not contain \(a^{k+1}\text{.}\) This gives a total of \(2^k + 2^k = 2\cdot 2^k = 2^{k+1}\) subsets of \(A\text{.}\) But our choice of \(A\) was arbitrary, so this works for any subset containing \(k+1\) elements, so \(P(k+1)\) is true. Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)
PrevTopNext