The idea here is the same as for regular mathematical induction. However, in the strong form, we allow ourselves more than just the immediately preceding case to justify the current case.
If the first case \(P(1)\) is true, and \(P(1) \lgccond P(2)\text{,}\) then \(P(2)\) must be true as well. Now, if \(P(1) \lgcand P(2) \lgccond P(3)\text{,}\) and we already have \(P(1)\) and \(P(2)\) both true, then \(P(3)\) must be true as well. Furthermore, if \(P(1) \lgcand P(2) \lgcand P(3) \lgccond P(4)\text{,}\) and we already have \(P(1)\text{,}\)\(P(2)\text{,}\) and \(P(3)\) all true, then \(P(4)\) must be true as well. And so on, until we have reached \(P(n)\text{,}\) for \(n\) whatever value we wish.
Procedure7.3.2.Proof by strong induction.
Base case.
Start by proving the statement for the base case \(n = 1\text{.}\)
Induction step.
Next, assume that \(k\) is a fixed number such that \(k \ge 1\text{,}\) and that the statement is true for all \(n \le k\text{.}\) Based on this assumption, try to prove that the next case, \(n=k+1\text{,}\) is also true.
Worked Example7.3.3.
Prove that each whole number greater than \(1\) can be factored into a product of (one or more) primes.
The first number greater than \(1\) is \(n = 2\text{,}\) and it is prime. So it can be considered a product of one prime.
Induction step.
Let \(k\) represent a whole number that is greater than \(1\text{.}\) Assume that \(2,3,4,\dotsc,k\) can each be factored into primes. We want to show \(k + 1\) can also be factored into primes.
Break into cases.
Case \(k + 1\) prime.
In this case \(k+1\) is already a product of a single prime, itself.
Case \(k + 1\) not prime.
If \(k + 1\) is not prime, then it has nontrivial divisors. So there exist integers \(m_1,m_2\text{,}\) with \(2\le m_1, m_2 \le k\text{,}\) such that \(k+1 = m_1 m_2\text{.}\) By our induction hypothesis, each of \(m_1,m_2\) can be factored into a product of primes, so their product \(k+1\) can as well.
Warning7.3.4.
If your proof of the induction step requires knowing a very specific number of previous cases are true, you may need to use a variant of the strong form of mathematical induction where several base cases are first proved. For example, if, in the induction step, proving that \(P(k+1)\) is true relies specifically on knowing that both \(P(k-1)\) and \(P(k)\) are true, then this argument does not prove that \(P(1)\lgccond P(2)\text{,}\) and so you must prove both base cases of \(P(1)\)and\(P(2)\) explicitly.
