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{.}\)

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.

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{.}\)

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 =\)

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.

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.

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{.}\)

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 =\)

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 =\)

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.

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.

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.

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{.}\)

17.

Prove using induction that every set containing \(n\) elements has \(2^n\) different subsets for any \(n \ge 1\text{.}\)
You have attempted of activities on this page.
<Prev^TopNext>
Authored in PreTeXt
Hosted on Runestone