Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 4.3 Mathematical Induction

In this section, we consider statements which involve some form of “... is true of every integer”. For example,
  • For every integer \(n \ge 1\text{,}\) \(\ds 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\text{.}\)
  • \(\log(a^n) = n \log (a)\) for every positive integer \(n\)
These are sequences of statements and we’ll be using a recursive technique to prove them, because we can’t prove that a statement like this is true by showing it’s true for every literal integer (there are infinitely many of them, so that’s impossible). Instead, the principle of mathematical induction tells us we can prove statements like these are true, so long as we do it just right. This section helps us learn how to do just that.

Subsection

Definition 4.3.1. Mathematical Induction.

To prove that a statement \(P(n)\) is true for all integers \(n\ge 0\text{,}\) we use the principle of math induction. The process has two core steps:
  1. Basis step: Prove that \(P(0)\) is true.
  2. Inductive step: Assume that \(P(k)\) is true for some value of \(k \ge 0\) and show that \(P(k+1)\) is true.
Video / Answer.
The common analogy for induction is to imagine an infinite ladder. First, you put your foot on the bottom rung. If you’re able to go from the \(k\)-th rung to the \(k+1\)-st rung, you’ll be able to climb forever.

Example 4.3.2.

The model of induction will always follow the following structure:
Proof.
Proof by math induction.
  1. Basis step. [here you prove \(P(0)\) is true]
  2. Inductive step. Assume \(P(k)\) is true for some \(k\ge 0\) [explicitly say what this statement is. This is called the inductive hypothesis]. We will show \(P(k+1)\) is true.
    [here you actually prove \(P(k+1)\) is true. You should use the inductive hypothesis. If you didn’t, you’ve made an error somewhere]

Example 4.3.3.

Prove that \(\ds 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\text{.}\)
Video / Answer.

Example 4.3.4.

Prove that \(a + ar + ar^2 + ar^3 + \dots + ar^n = \frac{ar^{n+1}-a}{r-1}\) if \(r \ne 1\text{.}\)
Video / Answer.

Example 4.3.5.

  1. Find a formula for \(\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \dots + \frac{1}{n(n+1)}\) for \(n\ge 1\) by examining small values of \(n\text{.}\)
  2. Prove the conjecture you just made.
Video / Answer.

Example 4.3.7.

What is wrong with the following “proof” that all horses are the same color?
Proof by induction:
  • Base step: the statement \(P(1)\) is the statement “one horse is the same color as itself”. This is clearly true.
  • Induction step: Assume that \(P(k)\) is true for some integer \(k\text{.}\) That is, any group of \(k\) horses are all the same color.
    Consider a group of \(k+1\) horses. Let’s line them up. If we look at first \(k\) horses, our induction hypothesis tells us they are the same color. Similarly, if we look at the last \(k\) horses, they are also the same color. This shows that all \(k+1\) horses are the same color.
Thus, by math induction, all horses are the same color.

Subsection

The next definition says “strong induction”, and I’m following the convention of nearly every discrete math book ever in defining this with its own name. The two concepts are really not very different, as we’ll see below.

Definition 4.3.8. Strong Induction.

The principal of strong math induction is like the so-called weak induction, except instead of proving \(P(k) \to P(k+1)\text{,}\) we assume that \(P(m)\) is true for all values of \(m\) such that \(0 \le m \le k\text{,}\) and we show that the next statement, \(P(k+1)\text{,}\) is true.

Example 4.3.9.

Let \(P(n)\) be the statement that “postage of \(n\) cents can be formed using just 4 cent and 7 cent stamps”. Prove \(P(n)\) is true for \(n\ge 18\text{.}\)
Video / Answer.
Here’s a different approach to the problem. If we can construct \(18, 19, 20, \dots k\) postage using the four and seven cent stamps, then for the \(k+1\) cent postage, We’ll just pretend you asked for four cents less! \(k+1 -4 = k-3\text{.}\) Were’re guaranteed to be able to make the postage by the induction hypothesis. Imagine putting those stamps on the package. Then all we need is to glue on one four cent stamp and we’re good to go!
Solution.
Here’s one way to approach the problem. Begin by showing we can do the basis, see if we can find a pattern, then make a formal proof:
  • \(\displaystyle 18 = 7\cdot2 + 4\cdot1\)
  • \(\displaystyle 19 = 7\cdot1 + 4\cdot3\)
  • \(\displaystyle 20 = 7\cdot0 + 4\cdot5\)
  • \(\displaystyle 21 = 7\cdot3 + 4\cdot0\)
  • \(\displaystyle 22 = 7\cdot2 + 4\cdot2\)
  • \(\displaystyle 23 = 7\cdot1 + 4\cdot4\)
  • \(\displaystyle 24 = 7\cdot0 + 4\cdot6\)
  • \(\displaystyle 25 = 7\cdot3 + 4\cdot1\)
  • \(\displaystyle 26 = 7\cdot2 + 4\cdot3\)
  • \(\displaystyle 27 = 7\cdot1 + 4\cdot5\)
  • \(\displaystyle 28 = 7\cdot0 + 4\cdot7\)
Do you notice a pattern? Take a couple moments to think about it, then let’s do the proof.
Proof.
Basis step: We can form 18 cent postage using two 7 and one 4 cent stamp.
Inductive step: Assume that one can form postage for all values from 18 cents up to \(k\) cents. Now we’re asked to form \(k+1\) cents. we know that we can form \(k\) cents, so, without loss of generality, let’s assume that it takes \(s\) 7 cent stamps and \(t\) 4 cent stamps. That is:
\begin{equation*} k = 7s + 4t \end{equation*}
Now, if \(s \ge 1\text{,}\) then we can do the following, adding one to both sides in two different ways:
\begin{equation*} k+1 = 7s + 4t - 7 + 8 \end{equation*}
Combining like terms we have
\begin{equation*} k+1 = 7(s-1) + 4(t+2) \end{equation*}
If, on the other hand, \(s=0\text{,}\) then we need to add one in a different way:
\begin{equation*} k+1 = 7s + 4t + 21 - 20 \end{equation*}
or, combining like terms:
\begin{equation*} k+1 = 7(s+3) + 4(t-5) \end{equation*}
Thus, by inductive hypothesis, if we can form \(k\) cents, I can form \(k+1\) cents postage.
Therefore, by mathematical induction, every postage cost greater than or equal to 18 can be formed using 4 and 7 cent stamps.

Example 4.3.10.

Prove that every positive integer has a binary expansion, that is, it is either a power of two or it is a sum of distinct powers of two.
Video / Answer.

Note 4.3.11. The difference between ’weak’ and ’strong’ induction.

’Regular’/’weak’ induction follows the pattern:
  1. Basis step.
  2. Inductive hypothesis is \(P(k)\) is true
  3. We show that \(P(k)\) implies that \(P(k+1)\) is true
That is, we use this induction process for claims where it’s convenient to show that the pattern follows sequentially in a convenient way. Straight-forward examples are the addition formulas;
’Strong’ induction follows the pattern:
  1. Basis step(s). [may need more than one basis, just like some recurrence relations]
  2. Inductive hypothesis is that all of \(P(1), P(2), P(3), \dots P(k)\) are true. [this is the ’strong’ part; it’s a larger assumption]
  3. We show that the hypothesis implies the next element in the sequence, \(P(k+1)\text{,}\) is true [like before]
the difference between this and the previous induction process is that it’s sometimes not convenient to prove that \(P(k)\) directly connects to \(P(k+1)\text{.}\) Instead, we still need to show that the next element in the sequence \(P(k+1)\) is true by appealing to a previous element in the sequence.
Relevant examples are those like the binary representation of a number - that \(k\) has a binary representation doesn’t immediately tell us \(k+1\) does, but if we can cut the number in half and use the binary representation of that number to scale-up in order to build a binary representation of \(k+1\text{.}\)
We separate ’weak’ and ’strong’ induction, but they’re really all the same thing. It’s just that when it’s convenient to show \(P(k) \to P(k+1)\text{,}\) we write fewer words for our inductive hypothesis. Because if we don’t need to use the fact that \(P(m)\) is true for all \(1 \le m \le k\text{,}\) then we just omit that. Mathematicians are lazy.

Subsection Computer Corner

You’ll be using mathematical induction when you’re designing algorithms. Let’s take the example of sorting a dataset. To prove that an algorithm is correct, you need:
  1. There is a valid base case. In our example - it can sort a set of one element)
  2. Assume the algorithm works for \(n\) objects. It can sort a set of \(n\) objects
  3. Show that if you have a larger set of one more object, \(n+1\) objects, your algorithm correctly sorts that new elements with the previous \(n\) elements. It can sort a set with \(n+1\) objects. Therefore, the algorithm is correct.
For example, we proved mathematically in Example 4.3.9 that any postage over 18 cents can be made with 4 and 7 cent stamps. The proof of that gives rise to an algorithm that we know must be correct:

Exercises Exercises

1.

Use induction to prove for all \(n \in \N\) that \(\d 1 + 2 + 2^2 + 2^3 + \dots + 2^n = 2^{n+1} - 1\text{.}\)
Solution.
Proof.
We must prove that \(1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1\) for all \(n \in \N\text{.}\) Thus let \(P(n)\) be the statement \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case, \(P(0)\text{,}\) which claims that \(1 = 2^{0+1} -1\text{.}\) Since \(2^1 - 1 = 2 - 1 = 1\text{,}\) we see that \(P(0)\) is true. Now for the inductive case. Assume that \(P(k)\) is true for an arbitrary \(k \in \N\text{.}\) That is, \(1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}\) We must show that \(P(k+1)\) is true (i.e., that \(1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1\)). To do this, we start with the left-hand side of \(P(k+1)\) and work to the right-hand side:
\begin{align*} \amp ~ 1 + 2 + 2^2 + \cdots + 2^k + 2^{k+1} \\ \amp= 2^{k+1} - 1 + 2^{k+1} \amp \text{by inductive hypothesis}\\ \amp = 2\cdot 2^{k+1} - 1 \amp\\ \amp= 2^{k+2} - 1 \amp \end{align*}
Thus \(P(k+1)\) is true so by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)

2.

Prove that \(1 + 3 + 5 + \cdots + (2n-1) = n^2\) for all \(n \ge 1\text{.}\)
Solution.
Proof.
Let \(P(n)\) be the statement \(1+3 +5 + \cdots + (2n-1) = n^2\text{.}\) We will prove that \(P(n)\) is true for all \(n \ge 1\text{.}\) First the base case, \(P(1)\text{.}\) We have \(1 = 1^2\) which is true, so \(P(1)\) is established. Now the inductive case. Assume that \(P(k)\) is true for some fixed arbitrary \(k \ge 1\text{.}\) That is, \(1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}\) We will now prove that \(P(k+1)\) is also true (i.e., that \(1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2\)). We start with the left-hand side of \(P(k+1)\) and work to the right-hand side:
\begin{align*} 1 + 3 + 5 + \cdots + (2k-1) + (2k+1) ~ \amp = k^2 + (2k+1) \amp \text{by ind. hyp.}\\ \amp = (k+1)^2 \amp \text{by factoring} \end{align*}
Thus \(P(k+1)\) holds, so by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)

3.

Prove that \(2^n \lt n!\) for all \(n \ge 4\text{.}\) (Recall, \(n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\text{.}\))
Solution.
Proof.
Let \(P(n)\) be the statement \(2^n \lt n!\text{.}\) We will show \(P(n)\) is true for all \(n \ge 4\text{.}\) First, we check the base case and see that yes, \(2^4 \lt 4!\) (as \(16 \lt 24\)) so \(P(4)\) is true. Now for the inductive case. Assume \(P(k)\) is true for an arbitrary \(k \ge 4\text{.}\) That is, \(2^k \lt k!\text{.}\) Now consider \(P(k+1)\text{:}\) \(2^{k+1} \lt (k+1)!\text{.}\) To prove this, we start with the left side and work to the right side.
\begin{align*} 2^{k+1}~ \amp = 2\cdot 2^k \amp\\ \amp \lt 2\cdot k! \amp \text{by the inductive hypothesis}\\ \amp \lt (k+1) \cdot k! \amp \text{ since } k+1 \gt 2\\ \amp = (k+1)! \amp \end{align*}
Therefore \(2^{k+1} \lt (k+1)!\) so we have established \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \ge 4\text{.}\)

4.

Prove that the sum of \(n\) squares can be found as follows
\begin{equation*} 1^2 +2^2 +3^2+...+n^2 = \frac{n(n+1)(2n+1)}{6} \end{equation*}
Solution.
Proof.
Let \(P(n)\) be the statement “\(1^2 +2^2 +3^2+...+n^2 = \frac{n(n+1)(2n+1)}{6}\)”. For the base case, we show that \(P(1)\) is true. That is:
\begin{equation*} P(1) := 1^2 = \frac{1(1+1)(2\cdot1+1)}{6} \end{equation*}
which is true.
For the inductive step, assume that \(P(k)\) is true for some integer \(k \ge 1\text{,}\) that is
\begin{equation*} 1^2 +2^2 +3^2+...+k^2 = \frac{k(k+1)(2k+1)}{6} \end{equation*}
and consider the statement:
\begin{align*} \amp ~1^2 + 2^2 + 3^2 + \dots + k^2 + (k+1)^2 \\ \amp = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ \amp = \frac{k(k+1)(2k+1)}{6} \frac{6(k+1)^2}{6} \\ \amp = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \\ \amp = \frac{(k+1)[2k^2 + k + 6k+6]}{6} \\ \amp = \frac{(k+1)[2k^2 + 7k+6]}{6} \\ \amp = \frac{(k+1)[(2k+3)(k+2)]}{6} \\ \amp = \frac{(k+1)(2(k+1)+1)((k+1) + 1)}{6} \end{align*}
which is exactly what we needed to show. Thus, by the principle of mathematical induction, the original statement \(1^2 +2^2 +3^2+...+n^2 = \frac{n(n+1)(2n+1)}{6}\) is true for all integers \(n\ge 1\text{.}\)

5.

What is wrong with the following “proof” of the “fact” that \(n+3 = n+7\) for all values of \(n\) (besides of course that the thing it is claiming to prove is false)?
Proof.
Let \(P(n)\) be the statement that \(n + 3 = n + 7\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) Assume, for induction that \(P(k)\) is true. That is, \(k+3 = k+7\text{.}\) We must show that \(P(k+1)\) is true. Now since \(k + 3 = k + 7\text{,}\) add 1 to both sides. This gives \(k + 3 + 1 = k + 7 + 1\text{.}\) Regrouping \((k+1) + 3 = (k+1) + 7\text{.}\) But this is simply \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\text{.}\)
Solution.
The only problem is that we never established the base case. Of course, when \(n = 0\text{,}\) \(0+3 \ne 0+7\text{.}\)

6.

The proof in the previous problem does not work. But if we modify the “fact,” we can get a working proof. Prove that \(n + 3 \lt n + 7\) for all values of \(n \in \N\text{.}\) You can do this proof with algebra (without induction), but the goal of this exercise is to write out a valid induction proof.
Solution.
Proof.
Let \(P(n)\) be the statement that \(n + 3 \lt n + 7\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) First, note that the base case holds: \(0+3 \lt 0+7\text{.}\) Now assume for induction that \(P(k)\) is true. That is, \(k+3 \lt k+7\text{.}\) We must show that \(P(k+1)\) is true. Now since \(k + 3 \lt k + 7\text{,}\) add 1 to both sides. This gives \(k + 3 + 1 \lt k + 7 + 1\text{.}\) Regrouping \((k+1) + 3 \lt (k+1) + 7\text{.}\) But this is simply \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\text{.}\)

7.

Find the flaw in the following “proof” of the “fact” that \(n \lt 100\) for every \(n \in \N\text{.}\)
Proof.
Let \(P(n)\) be the statement \(n \lt 100\text{.}\) We will prove \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case: when \(n = 0\text{,}\) \(P(n)\) is true, because \(0 \lt 100\text{.}\) Now for the inductive step, assume \(P(k)\) is true. That is, \(k \lt 100\text{.}\) Now if \(k \lt 100\text{,}\) then \(k\) is some number, like 80. Of course \(80+1 = 81\) which is still less than 100. So \(k +1 \lt 100\) as well. But this is what \(P(k+1)\) claims, so we have shown that \(P(k) \imp P(k+1)\text{.}\) Thus by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)
Solution.
The problem here is that while \(P(0)\) is true, and while \(P(k) \imp P(k+1)\) for some values of \(k\text{,}\) there is at least one value of \(k\) (namely \(k = 99\)) when that implication fails. For a valid proof by induction, \(P(k) \imp P(k+1)\) must be true for all values of \(k\) greater than or equal to the base case.

8.

What is wrong with the following “proof” of the “fact” that for all \(n \in \N\text{,}\) the number \(n^2 + n\) is odd?
Proof.
Let \(P(n)\) be the statement “\(n^2 + n\) is odd.” We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) Suppose for induction that \(P(k)\) is true, that is, that \(k^2 + k\) is odd. Now consider the statement \(P(k+1)\text{.}\) Now \((k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\text{.}\) By the inductive hypothesis, \(k^2 + k\) is odd, and of course \(2k + 2\) is even. An odd plus an even is always odd, so therefore \((k+1)^2 + (k+1)\) is odd. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)
Hint.
Rather than give a solution, here’s just a hint. What happens if \(n\) is even?

9.

Now give a valid proof (by induction, even though you might be able to do so without using induction) of the statement, “for all \(n \in \N\text{,}\) the number \(n^2 + n\) is even.”
Solution.
Proof.
Let \(P(n)\) be the statement “\(n^2 + n \) is even.”
Basis step: when \(n = 0\) we have \(0^0 + 0 = 0\) which is a even.
Inductive step: Assume that \(P(k)\) is true for some integer \(k \ge 0\text{,}\) that is, \(k^2 + k\) is even, and let’s consider the following:
\begin{align*} (k+1)^2 + (k+1) \amp = k^2 + 2k + 1 + k + 1 \\ \amp = k^2 + 3k + 2 \\ \amp = k^2 + k + 2k + 2 \end{align*}
now \(k^2 + k = 2l\) for some integer \(l\) by inductive hypothesis, so we have:
\begin{align*} (k+1)^2 + (k+1) \amp = k^2 + k + 2k + 2 \\ \amp = 2l + 2k + 2 \\ \amp = 2(l + k + 1) \end{align*}
and thus \((k+1)^2 + (k+1)\) is even.
Therefore, by math induction, \(n^2 + n\) is even for all natural numbers
.

10.

Use induction to prove that if \(n\) people all shake hands with each other, that the total number of handshakes is \(\frac{n(n-1)}{2}\text{.}\)
Solution.
Proof.
Let \(P(n)\) be the statement “when \(n\) people shake hands with each other, there are a total of \(\frac{n(n-1)}{2}\) handshakes.”
Base case: When \(n=2\text{,}\) there will be one handshake, and \(\frac{2(2-1)}{2} = 1\text{.}\) Thus \(P(2)\) is true.
Inductive case: Assume \(P(k)\) is true for arbitrary \(k\ge 2\) (that the number of handshakes among \(k\) people is \(\frac{k(k-1)}{2}\text{.}\) What happens if a \(k+1\)st person shows up? How many new handshakes take place? The new person must shake hands with everyone there, which is \(k\) new handshakes. So the total is now \(\frac{k(k-1)}{2} + k = \frac{(k+1)k}{2}\text{,}\) as needed.
Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 2\text{.}\)

11.

Use the product rule for logarithms (\(\log(ab) = \log(a) + \log(b)\)) to prove, by induction on \(n\text{,}\) that \(\log(a^n) = n \log(a)\text{,}\) for all natural numbers \(n \ge 2\text{.}\)
Solution.
The idea here is that if we take the logarithm of \(a^n\text{,}\) we can increase \(n\) by 1 if we multiply by another \(a\) (inside the logarithm). This results in adding 1 more \(\log(a)\) to the total.
Proof.
Let \(P(n)\) be the statement \(\log(a^n) = n \log(a)\text{.}\) The base case, \(P(2)\) is true, because \(\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}\) by the product rule for logarithms. Now assume, for induction, that \(P(k)\) is true. That is, \(\log(a^k) = k\log(a)\text{.}\) Consider \(\log(a^{k+1})\text{.}\) We have
\begin{equation*} \log(a^{k+1}) = \log(a^k\cdot a) = \log(a^k) + \log(a) = k\log(a) + \log(a) \end{equation*}
with the last equality due to the inductive hypothesis. But this simplifies to \((k+1) \log(a)\text{,}\) establishing \(P(k+1)\text{.}\) Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 2\text{.}\)

12.

Let \(f_1, f_2,\ldots, f_n\) be differentiable functions. Prove, using induction, that
\begin{equation*} (f_1 + f_2 + \cdots + f_n)' = f_1' + f_2' + \cdots + f_n' \end{equation*}
You may assume \((f+g)' = f' + g'\) for any differentiable functions \(f\) and \(g\text{.}\) (You don’t actually need to know calculus to be able to do this).
Hint.
You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, then apply the usual sum of derivatives rule, and then the inductive hypothesis.

13.

Recall that \(F_n\) is the \(n\)th Fibonacci number defined in Example 4.1.5.
Prove, by mathematical induction, that \(F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{.}\)
Solution.
Proof.
Let \(P(n)\) be the statement “\(F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{.}\)”
Basis step: if \(n = 0\) then \(F_0 = 0\) while \(F_{n+2} - 1 = 1 - 1 = 0\) so the basis step is true.
Inductive step: Assume that \(P(k)\) is true for some integer \(k \ge 0\text{.}\) That is, \(F_0 + F_1 + F_2 + \cdots + F_{k} = F_{k+2} - 1\text{.}\) Now consider
\begin{align*} \amp ~ F_0 + F_1 + F_2 + \dots F_k + F_{k+1}\amp\\ \amp= ( F_{k+2} - 1 ) + F_{k+1} \amp \text{by inductive hypothesis}\\ \amp= F_{k+2} + F_{k+1} - 1 \amp\\ \amp= F_{k+3} - 1 \amp \text{by recursive definition} \end{align*}
thus \(P(k+1)\) is true.
Therefore, by math induction, \(F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\) for all natural numbers.

14.

Prove that \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\) where \(F_n\) is the \(n\)th Fibonacci number.
Solution.
Proof.
Let \(P(n)\) be the statement \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}\) We will show that \(P(n)\) is true for all \(n \ge 0\text{.}\) First the base case is easy because \(F_0 = 0\) and \(F_1 = 1\) so \(F_0 = F_1 - 1\text{.}\) Now consider the inductive case. Assume \(P(k)\) is true, that is, assume \(F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}\) To establish \(P(k+1)\) we work from left to right:
\begin{align*} \amp F_0 + F_2 + \cdots + F_{2k} + F_{2k+2} \amp\\ \amp = F_{2k+1} - 1 + F_{2k+2} \amp \text{by inductive hypothesis} \\ \amp = F_{2k+1} + F_{2k+2} - 1 \amp\\ \amp = F_{2k+3} - 1 \amp \text{by recursive definition} \end{align*}
Therefore \(F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}\) which is to say \(P(k+1)\) holds. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 0\text{.}\)

15.

Prove, using strong induction, that every natural number is either a Fibonacci number or can be written as the sum of distinct Fibonacci numbers.
Solution.
Proof.
Let \(P(n)\) be the statement that \(n\) is either a Fibonacci number of the sum of distinct Fibonacci numbers
Basis step: For \(n=0\text{,}\) we have that \(0 = F_0\) is a Fibonacci number.
Inductive step: Assume that there is an integer \(k \ge 0\) such that \(P(m)\) is true for all \(0\le m \le k\text{.}\) That is, \(m\) is either a Fibonacci number or the sum of distinct Fibonacci numbers. Now let’s consider the next number, \(k+1\text{:}\)
Case 1: If \(k+1\) is a Fibonacci number, then we’re done.
Case 2: If \(k+1\) is not a Fibonacci number, then let \(F_m\) be the largest Fibonacci number less than \(k+1\text{.}\) Since \(k+1 - F_m \le k\) then we have that \(k+1 - F_m\) is the sum of distinct Fibonacci numbers, by inductive hypothesis.
Adding \(F_m\) to this sum gives us \(k+1 - F_m + F_m = k+1\) which then itself a sum of distinct Fibonacci numbers.
Thus, by induction, every natural number is either a Fibonacci number of the sum of distinct Fibonacci numbers.

16.

Prove, by mathematical induction, that \(F_1 + F_3 + F_5 + \dots + F_{2n -1} = F_{2n}\text{,}\) where \(F_n\) is the \(n\)th Fibonacci number.
Solution.
Proof.
Let \(P(n)\) be the statement “\(F_1 + F_3 + F_5 + \dots + F_{2n -1} = F_{2n}\)”
Basis step: If \(n =1\) then \(F_1 =1\) and \(F_{2\cdot 1} = 1\) so that \(P(1)\) is true.
Inductive step: Assume that \(P(k)\) is true for some integer \(k\ge 1\text{.}\) That is, \(F_1 + F_3 + F_5 + \dots + F_{2k -1} = F_{2k}\) and consider:
\begin{align*} \amp F_1 + F_3 + F_5 + \dots + F_{2k -1} + F_{2(k+1) - 1}\amp \\ \amp = F_1 + F_3 + F_5 + \dots + F_{2k -1} + F_{2k+1} \amp \\ \amp = F_{2k} + F_{2k+1} \amp \text{by inductive hypothesis} \\ \amp = F_{2k+2} \amp \text{by recursive definition}\\ \amp = F_{2(k+1)}\amp \end{align*}
And thus \(P(k+1)\) is true.
Therefore, by math induction, \(F_1 + F_3 + F_5 + \dots + F_{2n -1} = F_{2n}\) for all integers \(n\ge 1\text{.}\)

17.

Prove, by mathematical induction, that \(F_1^2 + F_2^2 + F_3^2 + \dots + F_n^2 = F_n \cdot F_{n+1}\text{,}\) where \(F_n\) is the \(n\)th Fibonacci number.
Hint.
\(F_{k+1}\left(F_{k} + F_{k+1}\right) = F_{k+1}F_{k+2} \)

18.

Prove that there is a strictly increasing sequence \(a_1, a_2, a_3, \ldots\) of numbers (not necessarily integers) such that \(a_n \lt 100\) for all \(n \in \N\text{.}\) (By strictly increasing we mean \(a_n \lt a_{n+1}\) for all \(n\text{.}\) So each term must be larger than the last.)
Solution.
Proof.
Let \(P(n)\) be the statement “there is a strictly increasing sequence \(a_1, a_2, \ldots, a_n\) with \(a_n \lt 100\text{.}\)” We will prove \(P(n)\) is true for all \(n \ge 1\text{.}\) First we establish the base case: \(P(1)\) says there is a single number \(a_1\) with \(a_1 \lt 100\text{.}\) This is true – take \(a_1 = 0\text{.}\) Now for the inductive step, assume \(P(k)\) is true. That is there exists a strictly increasing sequence \(a_1, a_2, a_3, \ldots, a_k\) with \(a_k \lt 100\text{.}\) Now consider this sequence, plus one more term, \(a_{k+1}\) which is greater than \(a_k\) but less than \(100\text{.}\) Such a number exists, for example, the average between \(a_k\) and 100. So then \(P(k+1)\) is true, so we have shown that \(P(k) \imp P(k+1)\text{.}\) Thus by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)

19.

Prove that 6 divides \(7^n - 1\) for all \(n \in \N\text{.}\)
Hint.
(Alternative idea to the below proof) In the inductive step add and subtract \(7^k\text{.}\) That is, you’ll have \(7\cdot 7^{k} - 1 - 7^k + 7^k\text{.}\) Now algebra.
Solution.
Proof.
Let \(P(n)\) be the statement “6 divides \(7^n - 1\text{.}\)” We will show \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case, \(P(0)\text{.}\) Since \(7^0 - 1 = 0\text{,}\) and \(0\) is a multiple of 6, \(P(0)\) is true. Now for the inductive case. Assume \(P(k)\) holds for an arbitrary \(k \in \N\text{.}\) That is, 6 divides \(7^k - 1\text{,}\) or in other words, \(7^k - 1 = 6j\) for some integer \(j\text{.}\) Now consider \(7^{k+1} - 1\text{:}\)
\begin{align*} 7^{k+1} - 1 ~ \amp = 7^{k+1} - 7 + 6 \amp \text{by cleverness:} -1 = -7 + 6\\ \amp = 7(7^k - 1) + 6 \amp \text{factor out a 7 from the first two terms}\\ \amp = 7(6j) + 6 \amp \text{by the inductive hypothesis}\\ \amp = 6(7j + 1) \amp \text{factor out a 6} \end{align*}
Therefore 6 divides \(7^{k+1} - 1\text{,}\) or in other words, \(P(k+1)\) is true. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)
<Prev^TopNext>