Strong induction

Strong induction

Ordinary induction (lesson PG3.1) assumes only the case before, $P(k)$, and proves $P(k + 1)$. Here $a_{k+1}$ needs both $a_k$ and $a_{k-1}$, so the step needs $P(k)$ and $P(k - 1)$ together.

Strong induction allows that. Its inductive step assumes every case up to $k$, not only the last one.

The argument of lesson PG3.1 shows that this is valid, without change. At the smallest failure $m$, every case below $m$ is true, which is exactly what the strong step assumes. So $P(m)$ holds after all, a contradiction.

How many base cases

Look at how far back the step reaches. Our step uses $a_{k-1}$, which exists only when $k - 1 \ge 1$. So it proves $P(k + 1)$ only for $k \ge 2$: it gives $P(3)$, $P(4)$ and so on, but never $P(2)$.

So $P(1)$ and $P(2)$ are both base cases, checked directly. The simulation showed what goes wrong without the second one. With a different $a_2$, the first term still fits, but the formula fails from $n = 2$ on.

In general, if the step reaches back $j$ cases, check the first $j$ cases directly. The step then covers every case after them.

A step that reaches further back

In the recursion, the step looks back one or two cases. Strong induction earns its name when the step needs a case far below $k$, and nobody can say in advance which one.

Take this claim: every whole number $n \ge 2$ is a prime or a product of primes. A prime is a whole number above 1 whose only divisors are 1 and itself, such as 2, 3, 5 and 7.

The function calls itself on smaller numbers, whichever they turn out to be. The proof does the same, by strong induction starting at $n = 2$ (lesson PG3.1 allows any start).

Base case. 2 is a prime.

Inductive step. Fix $k \ge 2$, and assume that every whole number $m$ with $2 \le m \le k$ is a prime or a product of primes. If $k + 1$ is prime, there is nothing to prove.

Otherwise $k + 1$ has a divisor $a$ with $1 < a < k + 1$, and $k + 1 = ab$ for a whole number $b$. Since $a \ge 2$, $b \le \frac{k + 1}{2} \le k$; since $a < k + 1$, $b \ge 2$. So $2 \le a \le k$ and $2 \le b \le k$.

By the hypothesis, $a$ and $b$ are each a prime or a product of primes. Putting the two lists of primes together writes $k + 1 = ab$ as a product of primes.

Conclusion. By strong induction, every whole number $n \ge 2$ is a prime or a product of primes.

The step needs the cases $a$ and $b$, which may lie far below $k$: 84 needs 2 and 42. Ordinary induction from the case 83 would not help, since 83 is prime and says nothing about 84.