Section 5.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 sections on induction, we will assume \(n\in \mathbb{Z}\text{.}\)
Strong induction requires a change in how we write our induction assumption, so we need a slight change to our standard structure for a strong induction proof.
Structure of a Strong Induction Proof.
-
Base Step.
Assume \(P(1)\) is true.
-
Induction Step.
Assume \(P(i)\) is true for all \(1\leq i\leq k\text{.}\) Show \(P(k+1)\) is true.
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{.}\) Thus, we may as well assume we have \(P(i)\) for everything up to \(P(k)\text{.}\)
To see the necessity of a stronger assumption, we revisit
Theorem 4.3.5, by using induction to prove every integer
\(n>1\) is divisible by a prime. First we will attempt to use regular induction and see why it isn’t enough.
Example 5.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 5.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 5.4.1.
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.
For the remainder of the section, we are going to switch gears a bit, a prove the existence part of the Quotient-Remainder Theorem. Before we do that we need the Well-Ordering Principle, which we will state without a proof.
Theorem 5.4.3. Well-Ordering Principle.
Let \(S\) be a set containing one or more integers, all of which are greater than some fixed integer. Then \(S\) has a least element.
To check that the Well-Ordering Principle applies, you need to check three things:
\(\displaystyle S\neq \emptyset\)
\(\displaystyle S\subseteq \mathbb{Z}\)
Every element of \(S\) is greater than some fixed integer.
Example 5.4.4. Well-Ordering Principle.
First note that the Well-Ordering Principle does not apply if the set is not integers. For example,
\begin{equation*}
\{1/n : n\in \mathbb{Z}, n\geq 1\}.
\end{equation*}
This is not a subset of the integers and does not have a least element, even though every element is greater than 0.
Now consider \(S=\{2k+1 : k\geq 0\}\text{.}\) Check each of the conditions.
\(S\neq \emptyset\) since \(1\in S\text{.}\)
\(S\subseteq \mathbb{Z}\) since \(2k+1\in \mathbb{Z}\text{.}\)
Every element of \(S\) is greater than some fixed integer since \(2k+1\geq 1\) when \(k\geq 0\text{.}\)
Activity 5.4.2.
Determine if the conditions of the Well-Ordering Principle apply to each of the following sets.
(a)
Let \(k\in \mathbb{Z}\text{,}\) \(S=\{2k: k\geq 3\}\text{.}\)
(b)
Let \(k, j\in \mathbb{Z}\text{,}\) \(S=\{2k+3j: 2k+3j\geq 0\}\text{.}\)
(c)
\(S=\{r\in \mathbb{Q}: r\geq 0\}?\)
Activity 5.4.3.
Give three elements of each set, then determine if the conditions of the Well-Ordering Principle apply to each of the following sets.
(a)
\(S=\{7-3k: 7-3k\geq 0, k\in \mathbb{Z}\}.\)
(b)
\(S=\{-8-3k: -8-3k\geq 0, k\in \mathbb{Z}\}.\)
(c)
Let \(n, d\in \mathbb{Z}\text{,}\) and \(d>0\text{,}\) \(S=\{n-dk: n-dk\geq 0, k\in \mathbb{Z}\}.\)
We now prove the existence part of the Quotient-Remainder Theorem.
Theorem 4.4.1: Given any
\(n, d\in \mathbb{Z}\) with
\(d>0\text{,}\) there exist
\(q, r\) such that
\(n=dq+r\) and
\(0\leq r< d\text{.}\)
Proof.
Let \(S=\{n-dk : n-dk\geq 0, k\in\mathbb{Z}\}\text{.}\) Show \(S\) satisfies the Well-Ordering Principle. Clearly \(S\) is a set of integers, and by definition, every element is greater than or equal to 0. So we just need to show that \(S\neq\emptyset\text{.}\)
If \(n\geq 0\text{,}\) we can let \(k=0\text{.}\) Then \(n-dk=n\geq 0\text{.}\) Hence \(n\in S\text{.}\)
If \(n< 0\text{,}\) let \(k=n\text{.}\) Then \(n-dn=n(1-d)\text{.}\) But \(n< 0\) and \(1-d\leq 0\text{.}\) Thus, \(n-dn\geq 0\text{.}\) Hence \(n-dn\in S\text{.}\)
Thus, \(S\) is nonempty and satisfies the conditions of the Well-Ordering Principle. Hence, \(S\) has a least element. Call it \(r\text{.}\)
Since \(r\in S\text{,}\) \(r=n-dk\) for some \(k\in \mathbb{Z}\text{.}\) Let \(k=q\text{.}\) Then \(r=n-dq\text{,}\) and so \(n=dq+r\text{.}\)
We just need to show that \(0\leq r< d\text{.}\) Well, \(r\geq 0\) since \(r\in S\text{.}\)
We will use contradiction to show \(r< d\text{.}\) Assume \(r\geq d\text{.}\) Then
\begin{align*}
n-d(q+1)&=n-dq-d\\
&=r-d\\
&\geq 0, \text{ since } r\geq d.
\end{align*}
But then \(n-d(q+1)\in S\) and \(n-d(q+1)< n-dq=r\text{.}\) This contradicts that \(r\) was the smallest element of \(S\text{.}\) Therefore, \(r< d\text{.}\)
Reading Questions Check Your Understanding
1.
True or false: \(S=\{\frac{3n+1}{4} : n\in \mathbb{Z}, n\geq 0\}\) satisfies the conditions of the Well-Ordering Principle.
True.
The elements aren’t all integers.
False.
The elements aren’t all integers.
2.
True or false: \(S=\{3n : n\in \mathbb{Z}, n\geq 0\}\) satisfies the conditions of the Well-Ordering Principle.
True.
Check that the set satifies the three conditions.
False.
Check that the set satifies the three conditions.
3.
True or false: \(S=\{-n : n\in \mathbb{Z}, n\geq 0\}\) satisfies the conditions of the Well-Ordering Principle.
True.
The elements aren’t all greater that some integer.
False.
The elements aren’t all greater that some integer.
4.
True or false: \(S=\{3n-k : n,k\in \mathbb{Z}, 3n-k\geq 0\}\) satisfies the conditions of the Well-Ordering Principle.
True.
Check that the set satifies the three conditions.
False.
Check that the set satifies the three conditions.
5.
True or false: \(S=\{(-1)^n : n\in \mathbb{Z}\}\) satisfies the conditions of the Well-Ordering Principle.
True.
Check that the set satifies the three conditions.
False.
Check that the set satifies the three conditions.
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_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-1}+a_{k-2}, k\geq3.
\end{equation*}
Use strong induction to prove that \(a_n\leq \Bigl(\frac{7}{4}\Bigr)^n\) for all integers \(n \geq 1\text{.}\)
You have attempted
of
activities on this page.
