5.2 Strong Induction & Well-Ordering

Ordinary induction climbs a ladder one rung at a time: $P (k) \Rightarrow P (k + 1)$ . Strong induction lets you stand on every rung below you at once. Use it when $P (k + 1)$ depends on a case further back than $P (k)$ .

Strong induction

Principle of strong induction

To prove $P (n)$ is true for all integers $n \geq b$ :

Basis step. Verify $P (b), P (b + 1), \dots, P (b + j)$ , as many cases as the inductive step needs.
Inductive step. Let $k \geq b + j$ be arbitrary. Assume $P (i)$ is true for every $i$ with $b \leq i \leq k$ . This is the strong inductive hypothesis. Use it to prove $P (k + 1)$ .

Conclude: by strong induction, $P (n)$ holds for all $n \geq b$ .

What changes vs. ordinary induction

	Ordinary induction	Strong induction
Inductive hypothesis	$P (k)$	$P (b) \land P (b + 1) \land \dots \land P (k)$
Base cases	usually one	often several
Use when	$P (k + 1)$ comes from $P (k)$	$P (k + 1)$ comes from $P (k - 1)$ , $P (k - 2)$ , a factor of $k + 1$ , …

Both are valid proof techniques and both are equivalent to the well-ordering property. Strong induction is never wrong to use, just sometimes unnecessary.

How many base cases do you need?

If your inductive step reaches back to $P (k + 1 - s)$ , you need $s$ consecutive base cases, and the inductive step starts once $k$ is at least the last base case.

Example: with 3-cent and 5-cent stamps you build $k + 1$ from $k - 2$ (add a 3-cent stamp), so $s = 3$ . You need 3 base cases, $P (8), P (9), P (10)$ , and the step is for $k \geq 10$ .

The postage-stamp template

This is the most common exam question for 5.2. Memorize the structure.

Every amount of postage of 12¢ or more can be formed using only 4¢ and 5¢ stamps.

Try writing the proof yourself first.

Model proof

Let $P (n)$ : "postage of $n$ cents can be formed using only 4-cent and 5-cent stamps." We prove $P (n)$ for all $n \geq 12$ by strong induction.

Basis step. We step back by 4, so we need 4 base cases:

$12 = 4 + 4 + 4$
$13 = 4 + 4 + 5$
$14 = 4 + 5 + 5$
$15 = 5 + 5 + 5$

So $P (12), P (13), P (14), P (15)$ are true.

Inductive step. Let $k \geq 15$ . Assume (strong IH) that $P (j)$ is true for all $j$ with $12 \leq j \leq k$ . We show $P (k + 1)$ .

Since $k \geq 15$ , we have $12 \leq k - 3 \leq k$ , so by the IH we can form $k - 3$ cents. Add one 4-cent stamp to get $(k - 3) + 4 = k + 1$ cents. So $P (k + 1)$ is true.

Conclusion. By strong induction, $P (n)$ is true for all $n \geq 12$ . ∎

Checklist for a full-credit strong induction proof

Define $P (n)$ in words.
Show every base case explicitly.
State the strong IH with the range: "assume $P (j)$ for all $b \leq j \leq k$ , where $k \geq$ (last base case)."
Show that the case you reach back to is inside that range, e.g. "since $k \geq 15$ , $k - 3 \geq 12$ ."
Finish with a conclusion sentence.

Common mistakes

Too few base cases. If you subtract 4, check that $k - 3 \geq 12$ , which needs $k \geq 15$ , so you need base cases up to 15.
Writing the IH as only " $P (k)$ " and then using $P (k - 3)$ . That's ordinary induction's hypothesis, so the proof is invalid.
Forgetting to justify that the earlier case is at least the starting value $b$ .

Finding which amounts are possible

Some questions say "determine which amounts can be formed" before asking for the proof. List small amounts until you get a run of consecutive successes as long as the smallest stamp; after that, everything works.

Which amounts can be formed with 3¢ and 5¢ stamps?

Possible: 3, 5, 6, 8, 9, 10, 11, 12, … Impossible: 1, 2, 4, 7.

From 8 on we have 8, 9, 10, three in a row (the smallest stamp is 3), so every amount $\geq 8$ works. Answer: 3, 5, 6, and every $n \geq 8$ .

Strong induction beyond stamps

Every integer

n \geq 2

is a product of primes.

Proof

Let $P (n)$ : " $n$ can be written as a product of primes." Basis: $2$ is prime, so it is a product of one prime.

Inductive step: Let $k \geq 2$ and assume $P (j)$ for all $2 \leq j \leq k$ . Consider $k + 1$ .

If $k + 1$ is prime, it is a product of one prime. Done.
Otherwise $k + 1 = ab$ with $2 \leq a \leq b < k + 1$ . By the strong IH both $a$ and $b$ are products of primes, so $k + 1 = ab$ is too.

Ordinary induction can't do this. Knowing $P (k)$ tells you nothing about the factors $a$ and $b$ of $k + 1$ . ∎

Fibonacci bound:

f_{n} < 2^{n}

for

n \geq 0

(where

f_{0} = 0

f_{1} = 1

f_{n} = f_{n - 1} + f_{n - 2}

)

Proof

Basis: $f_{0} = 0 < 1 = 2^{0}$ and $f_{1} = 1 < 2 = 2^{1}$ . We need two base cases because the recurrence looks back two steps.

Inductive step: Let $k \geq 1$ and assume $f_{j} < 2^{j}$ for all $0 \leq j \leq k$ . Then
$f_{k + 1} = f_{k} + f_{k - 1} < 2^{k} + 2^{k - 1} < 2^{k} + 2^{k} = 2^{k + 1} .$ ∎

The well-ordering property

Well-ordering property

Every nonempty set of nonnegative integers has a least element.

Which sets are well-ordered?

Yes: $N$ , $Z^{+}$ , ${n \in Z : n \geq - 5}$ (anything of the form "integers $\geq$ some fixed number").
No: $Z$ (no least element), $Q^{+}$ and $(0, 1)$ (keep halving), $R_{\geq 0}$ has least element 0 but its subset $(0, 1)$ has none.

Mathematical induction, strong induction, and well-ordering are equivalent: each one can be used to prove the others.

How it's used ("smallest counterexample"): Suppose the claim fails for some $n$ . The set of counterexamples is a nonempty set of nonnegative integers, so it has a least element $m$ . Then show a smaller counterexample exists (or $m$ isn't a counterexample), a contradiction.

Exam checklist

Write a complete strong induction proof (postage, bills, recurrences, products of primes).
Pick the right number of base cases and justify the reach-back.
State the difference between ordinary and strong IH.
Say what well-ordering is and decide whether a given set is well-ordered.