Section 4.4 Strong Induction
In this section we look at a variation on induction called strong induction. This is really just regular induction except we make a stronger assumption in the induction hypothesis. It is possible that we need to show more than one base case as well, but for the moment we will just look at how and why we may need to change the assumption.
Strong Induction.
Let \(P(n)\) be a property defined for integers \(n\text{.}\) If
\(P(1), \ldots P(a)\) are true for some \(a\text{,}\) and
if \(P(i)\) is true for all \(1\leq i\leq k\text{,}\) then \(P(k+1)\) is true;
then we can conclude \(P(n)\) is true for all \(n\geq 1\text{.}\)
As in the previous section, we will assume \(n\in \mathbb{Z}\text{.}\)
Structure of a Strong Induction Proof.
To prove \(P(n), \forall n\geq 1\text{,}\)
For now, we can use \(a=1\) in the base step and just do one base step as before. But we might need to show, say, \(P(1)\) and \(P(2)\text{.}\)
The only real difference between strong induction and regular induction is that instead of assuming \(P(k)\text{,}\) we assume \(P(1), P(2), \ldots P(k)\text{.}\) In notation, this is \(P(i)\) for all \(1\leq i\leq k\text{.}\)
Why can we change the assumption? Well, remember how induction works, first we show \(P(1)\text{,}\) then the induction step gets us to \(P(2)\text{,}\) which then gets us to \(P(3)\text{,}\) etc. But once we get to, say, \(P(4)\text{,}\) we already know \(P(1), P(2), P(3)\text{.}\) So we may as well assume we have \(P(i)\) for everything up to \(P(k)\text{.}\)
For the next two examples, we will look at proving every integer
\(n>1\) is divisible by a prime. Although we proved this using cases in
Theorem 3.3.2, we will now prove it using induction. First we will attempt to use regular induction and see why it isn't enough.
Example 4.4.1. Trying Regular Induction.
Prove for all integers \(n>1\text{,}\) \(n\) is divisible by a prime.
First we try to do the proof using regular induction.
Proof.
Base Step: Let \(n=2\text{.}\) Then \(2\mid 2\) and 2 is prime.
Thus, \(n\) is divisible by a prime.
Induction Step:
Assume \(k\) is divisible by a prime for some \(k\geq 2\text{.}\)
Show \(k+1\) is divisible by a prime.
“Proof” of induction step:
Case 1: \(k+1\) is prime. Now, \(k+1\mid k+1\) and hence \(k+1\) is divisible by a prime.
Case 2: \(k+1\) is not prime. This is were we get stuck, since although we know \(k\) is divisible by a prime, that doesn't tell us anything about \(k+1\text{.}\) In fact we showed that any prime dividing \(k\) CANNOT divide \(k+1\text{.}\)
Thus, regular induction is not going to work for this proof.
Now we can show how to do the proof with strong induction.
Example 4.4.2. Strong Induction.
Prove for all integers \(n>1\text{,}\) \(n\) is divisible by a prime.
The only change in the structure is to the induction assumption.
Proof.
Base Step: Let \(n=2\text{.}\) Then \(2\mid 2\) and 2 is prime.
Thus, \(n\) is divisible by a prime.
Induction Step:
Assume \(i\) is divisible by a prime for all \(2\leq i\leq k\) and for some \(k\geq 2\text{.}\)
Show \(k+1\) is divisible by a prime.
Proof of induction step:
Case 1: \(k+1\) is prime. Now, \(k+1\mid k+1\) and hence \(k+1\) is divisible by a prime.
Case 2: \(k+1\) is not prime. Thus \(k+1=ab\) where \(1< a < k+1\text{.}\) Then \(2\leq a\leq k\text{.}\) By our induction assumption, \(a\) must be divisible by a prime. Since \(a\mid k+1\) and \(a\) is divisible by a prime, \(k+1\) is divisible by a prime.
Thus, by induction, every \(n>1\) is divisible by a prime.
In regular induction, we use that we know the statement holds for \(k\) to get that it holds for \(k+1\text{.}\) Strong induction is useful when we need to use some smaller case (not just \(k\)) to get the statement for \(k+1\text{.}\)
Activity 4.4.1. Strong Induction on a Sequence.
Let \(a_0, a_1, a_2, \ldots\) be the sequence defined as
\begin{equation*}
a_0=1, a_1=2, a_2=3
\end{equation*}
\begin{equation*}
a_k=a_{k-1}+a_{k-2}+a_{k-3}, k\geq3.
\end{equation*}
(a)
Write out the first 6 terms of the sequence.
(b)
Convince yourself that for the first six terms of the sequence, \(a_n\leq 3^n\text{.}\)
(c)
Now try to write a standard induction proof to prove \(a_n\leq 3^n\) for all \(n\geq 0\text{.}\) Does anything go wrong?
(d)
The proof requires strong induction. For the base step, how many previous terms do you need before you can first compute \(a_k\) using the formula provided in defining the sequence? You need to show the base step for each of these initial terms since the induction won't apply to them. Check the base step for each of these terms.
(e)
Write the “assume” and “show” statements for the inductive step. Make sure your “assume” statement is in the form for strong induction.
(f)
Now prove the inductive step.
As we see in
Activity 4.4.1, strong induction is a useful technique for proving statements about sequences. One particularly nice sequence is the
Fibonacci Sequence.
Definition 4.4.3.
The Fibonacci sequence is the sequence, \(f_n\text{,}\) defined by
\begin{equation*}
f_1=1, f_2=1, f_n=f_{n-1}+f_{n-2}.
\end{equation*}
The first two terms are called the initial terms. Then we generate terms by adding the previous two terms. For example, \(f_3=f_2+f_1=1+1=2\text{.}\)
Activity 4.4.2. Generating the Fibonacci Sequence.
Find the first 8 terms of the Fibonacci sequence.
Activity 4.4.3. A Fibonacci Sum.
Consider the sum of every other Fibonacci number:
\begin{equation*}
\sum_{i=1}^{n}f_{2i-1}.
\end{equation*}
(a)
Make a table of \(n\) and the corresponding \(f_n\) for \(n=1\) to \(n=8\text{.}\)
(b)
For each \(n\) in your table, find the sum \(\sum_{i=1}^{n}f_{2i-1}\text{.}\)
(c)
Conjecture a formula for \(\sum_{i=1}^{n}f_{2i-1}\text{.}\)
(d)
Use induction to prove your formula.
Exercises Exercises
1.
Let \(a_1, a_2, a_3, \ldots\) be the sequence defined as
\begin{equation*}
a_1=1, a_2=3,
\end{equation*}
\begin{equation*}
a_k=a_{k-2}+2a_{k-1}, k\geq3.
\end{equation*}
Prove that \(a_n\) is odd for all integers \(n \geq 1\text{.}\)
2.
Let \(b_1, b_2, b_3, \ldots\) be the sequence defined as
\begin{equation*}
b_1=4, b_2=12,
\end{equation*}
\begin{equation*}
b_k=b_{k-2}+b_{k-1}, k\geq3.
\end{equation*}
Prove that \(b_n\) is divisible by 4 for all integers \(n \geq 1\text{.}\)
3.
Let \(c_1, c_2, c_3, \ldots\) be the sequence defined as
\begin{equation*}
c_1=3, c_2=5,
\end{equation*}
\begin{equation*}
c_k=3c_{k-1}-2c_{k-2}, k\geq3.
\end{equation*}
Prove that \(c_n=2^n+1\) for all integers \(n \geq 1\text{.}\)
4.
Let \(a_1, a_3, a_3, \ldots\) be the sequence defined as
\begin{equation*}
a_1=1, a_2=3,
\end{equation*}
\begin{equation*}
a_k=a_{k-1}+a_{k-2}, k\geq3.
\end{equation*}
Prove that \(a_n\leq \Bigl(\frac{7}{4}\Bigr)^n\) for all integers \(n \geq 1\text{.}\)
5.
Let \(f_1, f_2, f_3,\ldots\) be the Fibonacci numbers. Find and prove a formula for \(\sum_{i=1}^{n}f_{2i}\text{.}\)
6.
Let \(f_1, f_2, f_3,\ldots\) be the Fibonacci numbers. Find and prove a formula for \(f_n-f_{n-1}+f_{n-2}-\cdots+(-1)^{n+1}f_1\) when \(n\) is a positive integer.
7.
Let \(f_1, f_2, f_3,\ldots\) be the Fibonacci numbers. Prove for all \(n\geq 2\) and all \(m\geq 1\text{,}\) \(f_{n+m}=f_{n-1}f_m+f_nf_{m+1}\text{.}\)
8.
Let \(f_1, f_2, f_3,\ldots\) be the Fibonacci numbers. Prove for all \(n\geq 2\text{,}\) \(f_{n+1}f_{n-1}-(f_n)^2=(-1)^n\text{.}\)
9.
Prove if \(f_n\) is the \(n\)th Fibonacci number, then
\begin{equation*}
f_n={({1+\sqrt 5\over 2})^n-({1-\sqrt 5\over 2})^n\over \sqrt 5}.
\end{equation*}
10.
Hint.Let \(n\) stand for the number of connectives contained in any given statement \(A\text{.}\)
