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