In ordinary induction each case leans on the one just before it. Some arguments need to reach further back: a number splits into two smaller factors, or an amount of postage is a smaller amount plus one stamp. Strong induction allows exactly that.
Key idea
Strong induction: to prove $P(n)$ for all $n \ge n_{0}$, prove the base cases, then show that if $P(n_{0}), P(n_{0} + 1), \ldots, P(k)$ are all true, so is $P(k + 1)$. If the step uses the case $k + 1 - j$, you need $j$ consecutive base cases, because the first $j$ values have nothing to step from.
Why it works
Strong induction is no stronger than ordinary induction (each can be turned into the other), but it fits problems where case $k + 1$ depends on an earlier case that is not $k$. The base cases matter more: if the step reaches back $4$ places, it builds case $16$ from case $12$, case $17$ from $13$, and so on. Unless all four of $12$, $13$, $14$, $15$ are checked directly, some chain of cases never gets started.
Worked examples
Worked example: Postage with 4¢ and 5¢ stamps
Prove that every amount of at least 12¢ can be paid with 4¢ and 5¢ stamps.
- Base cases: $12 = 4 + 4 + 4$, $13 = 4 + 4 + 5$, $14 = 4 + 5 + 5$, $15 = 5 + 5 + 5$.
- Step: let $n \ge 16$ and assume every amount from $12$ to $n - 1$ can be paid. Then $n - 4 \ge 12$ can be paid; add one 4¢ stamp to pay $n$.
- The step reaches back $4$, which is why exactly four base cases were needed. (And $11$¢ really is impossible, so $12$ is the right start.)
Answer: Base cases 12, 13, 14, 15; step from $n - 4$.
Worked example: Products of primes
Prove that every integer $n \ge 2$ is a prime or a product of primes.
- Base case: $2$ is prime.
- Step: assume every integer from $2$ to $k$ is a prime or a product of primes, and look at $k + 1$.
- If $k + 1$ is prime, done. Otherwise $k + 1 = ab$ with $2 \le a, b \le k$. By the hypothesis, $a$ and $b$ are products of primes, so $ab$ is too.
- Ordinary induction would not help: knowing about $k$ says nothing about $k + 1$'s factors, which can be any smaller numbers.
Answer: Split $k + 1 = ab$ and apply the hypothesis to both factors.
Worked example: A sequence with two base cases
Let $a_{1} = 1$, $a_{2} = 3$ and $a_{n} = a_{n-1} + a_{n-2}$. Prove $a_{n} < 2^{n}$ for all $n \ge 1$.
- Base cases: $a_{1} = 1 < 2$ and $a_{2} = 3 < 4$. Two are needed because the step uses two earlier terms.
- Step: for $k + 1 \ge 3$, assume the claim for all smaller indices. Then $a_{k+1} = a_{k} + a_{k-1} < 2^{k} + 2^{k-1} < 2^{k} + 2^{k} = 2^{k+1}$.
Answer: Two base cases, then $a_{k+1} < 2^{k} + 2^{k-1} < 2^{k+1}$.
Common mistake
Checking one base case when the step reaches further back. For the postage problem, checking only $12$ and stepping from $n - 4$ proves $16, 20, 24, \ldots$ and nothing about $13$ or $17$. Check: if the step uses the case $j$ places back, verify $j$ consecutive starting cases.