Skip to main content
Logo image

Section 4.7 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 nth day is always a 5 for all nβ‰₯1.
  3. Find a closed formula for the nth 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 nth 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, 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 nth 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, 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 7+17+27+β‹―+2047.
Solution.
2054β‹…2042=209508.

2.

Consider the sequence 35,45,55,65,…,10n+5.
  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βˆ’3 terms.
  2. 10n+(βˆ’5).
  3. (10n+40)βˆ—(nβˆ’3)2.

3.

Consider the sequence given by an=6β‹…3nβˆ’1.
  1. Find the first 4 terms of the sequence.
    a1= , a2= , a3= , a4= ,...
    What sort of sequence is this?
    • arithmetic
    • geometric
    • neither
  2. Find the sum of the first 22 terms. That is, compute βˆ‘k=122ak.
Solution.
  1. 6,18,54,162,… The sequence is geometric.
  2. 6β‹…322βˆ’62=9.41432Γ—1010.

4.

Consider the sequence 5,11,19,29,41,55,…. Assume a1=5.
  1. Find a closed formula for an, the nth term of the sequence, by writing each term as a sum of a sequence. Hint: first find a0, 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 nth term of the sequence (an)nβ‰₯1 which starts,
16,27,40,55,72,…
Note the first term above is a1, not a0.
Solution.
an=n2+8n+7. Here we know that we are looking for a quadratic because the second differences are constant. So an=an2+bn+c. We can work backwards to find that a0=7, so we know c=7. Then solve the system,
16=a+b+727=4a+2b+7
to find a=1 and b=8.

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 a1=4, a2=6 and an=anβˆ’1+anβˆ’2.
  1. Write out the first 6 terms of the sequence.
  2. Could the closed formula for an be a polynomial? Explain.
Solution.
  1. 4,6,10,16,26,42,….
  2. No, taking differences gives the original sequence back, so the differences will never be constant.

8.

The sequence (an)nβ‰₯1 starts βˆ’1,0,2,5,9,14… and has closed formula an=(n+1)(nβˆ’2)2. Use this fact to find a closed formula for the sequence (bn)nβ‰₯1 which starts 4,10,18,28,40,….
Solution.
bn=(n+3)n.

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 an=2anβˆ’1+24anβˆ’2 with first two terms a0=10 and a1=12.
  1. Write out the first 5 terms of the sequence defined by this recurrence relation.
    a2= , a3= , a4= , ...
  2. Solve the recurrence relation. That is, find a closed formula for an.
Solution.
The sequence is 10,12,264,816,7968,…. It has closed formula an=(245)(βˆ’4)n+(265)β‹…6n, using the characteristic root technique.

11.

Consider the recurrence relation an=3anβˆ’1+18anβˆ’2 with first two terms a0=4 and a1=10.
  1. Find the next two terms of the sequence (a2 and a3):
    a2=
    a3=
  2. Solve the recurrence relation. That is, find a closed formula for an.
    an=
Solution.
The sequence is 4,10,102,486,3294,…. It has closed formula an=(149)(βˆ’3)n+(229)β‹…6n, 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 nth 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… starting with a0=2 and a1=2.
  2. an=anβˆ’1+2anβˆ’2. 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 an=a2n+b(βˆ’1)n, and we can find a and b to give an=432n+23(βˆ’1)n.

13.

Consider the sequence of partial sums of squares of Fibonacci numbers: F12, F12+F22, F12+F22+F32,…. The sequences starts 1,2,6,15,40,…
  1. Guess a formula for the nth 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!<nn for nβ‰₯2
  2. 11β‹…2+12β‹…3+13β‹…4+β‹―+1nβ‹…(n+1)=nn+1 for all n∈Z+.
  3. 4nβˆ’1 is a multiple of 3 for all n∈N.
  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)β‹…nn.
  2. Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions.
  3. Hint: Write 4k+1βˆ’1=4β‹…4kβˆ’4+3.
  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: 22=4. The inductive case: assume (2n)2 is divisible by 4 and consider (2n+2)2=(2n)2+4n+4. This is divisible by 4 because 4n+4 clearly is, and by our inductive hypothesis, so is (2n)2.

15.

Prove 13+23+33+β‹―+n3=(n(n+1)2)2 holds for all nβ‰₯1, by mathematical induction.
Hint.
This is a straight forward induction proof. Note you will need to simplify (n(n+1)2)2+(n+1)3 and get ((n+1)(n+2)2)2.

16.

Suppose a0=1, a1=1 and an=3anβˆ’1βˆ’2anβˆ’2. Prove, using strong induction, that an=1 for all n.
Hint.
There are two base cases P(0) and P(1). Then, for the inductive case, assume P(k) is true for all k<n. This allows you to assume anβˆ’1=1 and anβˆ’2=1. Apply the recurrence relation.

17.

Prove using induction that every set containing n elements has 2n different subsets for any nβ‰₯1.
Solution.
Let P(n) be the statement, β€œevery set containing n elements has 2n different subsets.” We will show P(n) is true for all nβ‰₯1. 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=21. Thus P(1) is true. Inductive case: Suppose P(k) is true for some arbitrary kβ‰₯1. Thus every set containing exactly k elements has 2k different subsets. Now consider a set containing k+1 elements: A={a1,a2,…,ak,ak+1}. Any subset of A must either contain ak+1 or not. In other words, a subset of A is just a subset of {a1,a2,…,ak} with or without ak+1. Thus there are 2k subsets of A which contain ak+1 and another 2k+1 subsets of A which do not contain ak+1. This gives a total of 2k+2k=2β‹…2k=2k+1 subsets of A. 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β‰₯1.