← mapLogic & Proof

Strong Induction & Well-Ordering

⚗ Dr. Möbius, from the lab

Ordinary induction lets you lean on one previous domino — the immediately prior $P(k)$ . But some proofs need to reach way back: to factor a number into primes, you might split it as $35 = 5 \times 7$ , and suddenly you need facts about $5$ and $7$ , not about $34$ . Your one measly domino is useless. Enter strong induction: assume every previous case at once. Then we meet its mirror twin, the Well-Ordering Principle — a statement so obvious-sounding that students ignore it right up until it saves their ass — and the slickest trick in all of proof: the smallest criminal.

THE BIG IDEA

Strong induction lets you assume P holds for all values up to k when proving P(k+1), and it is equivalent to the Well-Ordering Principle: every nonempty set of naturals has a least element.

When one domino back isn't enough

Ordinary induction hands you a single piece of free loot in the step: the immediately preceding case $P(k)$ . Usually that's plenty — sums and divisibility formulas connect $P(k+1)$ neatly to $P(k)$ . But sometimes the natural way to break down $P(k+1)$ reaches back further than one step, to cases you can't predict in advance.

Strong induction fixes this by handing you all the previous loot:

Base case(s). Prove $P$ for the starting value(s).
Strong inductive step. Prove that for every $k$ , if $P(1), P(2), \dots, P(k)$ all hold, then $P(k+1)$ holds.

The only difference from ordinary induction is the strong inductive hypothesis: instead of assuming just $P(k)$ , you assume every case from the base up through $P(k)$ . More free loot, same domino logic — if all earlier dominoes have fallen, the next one falls too, and the chain still reaches every natural number.

And here's the reassuring part: strong induction is not a more powerful axiom. Anything provable by strong induction is provable by ordinary induction and vice versa — they're logically equivalent. The Federation of Boring Textbook Authors loves to present them as separate, mysterious techniques; they're the same damn principle in two outfits. "Strong" refers only to the convenience of the hypothesis, not to extra deductive muscle. Use it whenever splitting $P(k+1)$ lands you on cases smaller than $k$ .

Worked: every integer ≥ 2 is a product of primes

This is the existence half of the Fundamental Theorem of Arithmetic — that every integer factors into primes — and it's the poster child for strong induction, because factoring a number splits it into two smaller numbers, not into " $n - 1$ ." Ordinary induction would be completely helpless here, which is why I need you to understand both tools.

Theorem. Every integer $n \ge 2$ is a product of one or more primes.

Proof (by strong induction on $n$ ).

Base case ( $n = 2$ ): $2$ is prime, so it's a product of a single prime (itself). ✓

Strong inductive step: Let $k \ge 2$ , and assume the strong IH: every integer $m$ with $2 \le m \le k$ is a product of primes. We must show $k + 1$ is a product of primes. Two cases:

$k+1$ is prime. Then it's a product of one prime (itself). Done.
$k+1$ is composite. By definition of composite, $k + 1 = a \cdot b$ for some integers $a, b$ with $2 \le a \le k$ and $2 \le b \le k$ (both factors are at least $2$ and strictly less than $k+1$ ). Now spend the strong IH on both $a$ and $b$ : since each lies in the range $[2, k]$ , each is a product of primes. Multiplying those two prime factorizations together expresses $k+1$ as a product of primes.

Either way, $k + 1$ is a product of primes. By strong induction, every integer $\ge 2$ is a product of primes. $\blacksquare$

Why ordinary induction can't do this cleanly: when you factor $k+1 = a \cdot b$ , the factors $a$ and $b$ could be anywhere in $[2, k]$ — not necessarily $k$ itself. You need the factorizations of $a$ and $b$ to be already available, and only the strong hypothesis ("everything up to $k$ works") guarantees that. This is exactly the situation strong induction was built for. (Recall: in proof-by-contradiction we used the fact that every integer $\ge 2$ has a prime factor, without proving it, to finish Euclid's theorem. We're now closing that debt. I don't leave debts open.)

The Well-Ordering Principle

Now a statement that looks almost too obvious to bother with, yet powers some of the cleanest proofs you'll ever write.

Well-Ordering Principle (WOP). Every nonempty subset of $\mathbb{N}$ has a least element.

That's it. Any nonempty collection of natural numbers, however weird and pathological, contains a smallest member. ("Nonempty" is essential — the empty set has no least element, having no elements at all, a fact that will bite you if you're sloppy.) This fails for other number systems: the positive rationals have no least element (whatever tiny positive fraction you name, half of it is smaller, and so on forever), and so do the integers as a whole (no least integer). WOP is special to $\mathbb{N}$ , riding on the successor structure from the very first lesson — you can't descend forever through the naturals, because there's a hard floor at $0$ . The reactor has a floor.

WOP is equivalent to induction. They prove each other; assuming one, you can derive the other. So you're free to use whichever makes a given proof shortest — they're the same principle in two outfits, and I want you comfortable in both.

Using WOP: the smallest counterexample

WOP unlocks a devastating proof style — really a flavor of proof by contradiction (from two lessons ago) — called the minimal criminal or smallest counterexample argument. The shape:

Suppose, for contradiction, the claim $P(n)$ is false for some naturals. Then the set $S$ of counterexamples (the $n$ where $P(n)$ fails) is nonempty.
By WOP, $S$ has a least element — call it $m$ , the smallest criminal: the smallest $n$ for which $P$ fails.
Derive a contradiction by producing an even smaller counterexample, or by showing $m$ can't actually fail $P$ . Since $m$ was the smallest criminal, an even smaller one is impossible — contradiction.
Therefore $S$ is empty: there are no counterexamples, so $P(n)$ holds for all $n$ . $\blacksquare$

The genius is step 3: by grabbing the minimal offender, you give yourself a powerful extra fact — everything below $m$ obeys the rule — and you weaponize it to break $m$ itself. It's strong induction wearing a trench coat, and it is deeply satisfying to watch. Let's see it bite.

Example claim. Every integer $n \ge 2$ has a prime divisor.

Proof (smallest counterexample via WOP). Suppose not. Then the set $S$ of integers $\ge 2$ with no prime divisor is nonempty, so by WOP it has a least element $m$ . Now $m$ has no prime divisor — in particular $m$ is not prime (a prime divides itself), so $m$ is composite: $m = a \cdot b$ with $2 \le a < m$ . Since $a < m$ and $m$ was the smallest criminal, $a$ is not a counterexample, so $a$ has a prime divisor $p$ . But $p \mid a$ and $a \mid m$ , so $p \mid m$ (divisibility is transitive — from Direct Proof). So $m$ has a prime divisor $p$ — contradicting $m \in S$ . Hence $S$ is empty, and every integer $\ge 2$ has a prime divisor. $\blacksquare$

That's the fact Euclid borrowed in the previous lesson. Notice how WOP, strong induction, and contradiction are really the same machine: "the smallest place it could go wrong can't actually go wrong, so nowhere does." Three names, one weapon — the same weapon that runs through every floor of this building. Now go wield it.

🔬 SPECIMENS (worked examples)

Worked example 1 — making postage from 4- and 5-cent stamps▸

Prove by strong induction: every integer amount of postage $n \ge 12$ cents can be made using only $4$ -cent and $5$ -cent stamps.

Proof (by strong induction on $n$ ).

Base cases ( $n = 12, 13, 14, 15$ ): $12 = 4+4+4$ ; $13 = 4+4+5$ ; $14 = 4+5+5$ ; $15 = 5+5+5$ . ✓ (We need four base cases because the step reaches back by $4$ .)

Strong step: Let $k \ge 15$ and assume the strong IH: every amount $m$ with $12 \le m \le k$ is makeable. Show $k + 1$ is makeable. Since $k + 1 \ge 16$ , the amount $(k+1) - 4 = k - 3$ satisfies $12 \le k - 3 \le k$ , so by the strong IH it's makeable. Take that combination of stamps and add one $4$ -cent stamp: that yields $(k - 3) + 4 = k + 1$ cents.

So $k+1$ is makeable. By strong induction, every $n \ge 12$ is makeable. $\blacksquare$

Why strong (and why four base cases)? The step reduces $k+1$ to $k - 3$ , four steps back — ordinary "one back" induction wouldn't reach it, and we must seed the first four values by hand so the recursion always lands on a covered case.

Worked example 2 — a least element forces a stop▸

Use the Well-Ordering Principle to prove: there is no sequence of natural numbers $n_1 > n_2 > n_3 > \cdots$ that strictly decreases forever.

Proof (by WOP). Suppose, for contradiction, that such an infinitely decreasing sequence of naturals exists: $n_1 > n_2 > n_3 > \cdots$ , all in $\mathbb{N}$ .

Consider the set $S = \{n_1, n_2, n_3, \dots\}$ of all terms. It is a nonempty subset of $\mathbb{N}$ (it contains $n_1$ , at least). By the Well-Ordering Principle, $S$ has a least element; say it's $n_j$ , the smallest value appearing in the sequence.

But the sequence strictly decreases, so $n_{j+1} < n_j$ , and $n_{j+1}$ is also a term of the sequence, hence in $S$ . That makes $n_{j+1}$ an element of $S$ smaller than the supposed least element $n_j$ — contradiction.

Therefore no infinitely decreasing sequence of naturals exists. $\blacksquare$

This "no infinite descent" fact is WOP's soul: you can't keep getting smaller forever inside $\mathbb{N}$ , because every nonempty collection hits a floor. It's exactly what makes minimal-criminal arguments terminate.

Worked example 3 — the trap: always check the factor bounds▸

In the proof that every $n \ge 2$ is a product of primes, a student writes: "if $k+1$ is composite, then $k + 1 = a \cdot b$ , and by the IH both $a$ and $b$ are products of primes." Identify the gap and fix it.

The gap: the student never checked that $a$ and $b$ actually fall in the range where the strong IH applies. The strong IH covers integers $m$ with $2 \le m \le k$ . If $a$ could be $1$ or $k+1$ , the IH says nothing about it, and the argument collapses.

The fix: invoke the definition of composite precisely. $k+1$ being composite means it has a factorization $k+1 = a \cdot b$ with both factors strictly between $1$ and $k+1$ , i.e. $2 \le a \le k$ and $2 \le b \le k$ . (If one factor were $1$ , the other would be $k+1$ and that's not a proper factorization; "composite" rules that out.) Now both $a$ and $b$ lie in $[2, k]$ , so the strong IH legitimately applies to each, and their prime factorizations multiply to give one for $k+1$ .

The lesson: strong induction is only as good as your bookkeeping on which earlier cases you're invoking. You must verify the cases you lean on are actually inside the hypothesis's range — here, that the factors are genuinely smaller than $k+1$ and at least $2$ . Skip that check and you've proven nothing. $\blacksquare$

☠ KNOWN HAZARDS

Thinking strong induction proves more than ordinary induction. It doesn't — they're equivalent. Reach for "strong" only because the hypothesis is handier, e.g. when factoring lands you on unpredictable smaller cases.
Forgetting "nonempty" in WOP. The empty set has no least element. Minimal-criminal proofs require the counterexample set to be nonempty — that's the assumption you're aiming to contradict.
Applying WOP to the wrong set. It holds for $\mathbb{N}$ , not for $\mathbb{Q}^+$ (no least positive rational — try finding one, I dare you) or $\mathbb{Z}$ (no least integer). Make sure your set lives inside $\mathbb{N}$ .
Splitting a composite without bounding the factors. In the prime-factorization proof you must note $2 \le a, b \le k$ so the strong IH actually applies to $a$ and $b$ . A factor of $1$ or $k+1$ breaks the argument.

TL;DR

▸
Strong induction: to prove $P(k+1)$ , assume the strong IH that $P(1), \dots, P(k)$ all hold — useful when $P(k+1)$ splits into cases smaller than $k$ .
▸
It's logically equivalent to ordinary induction — "strong" means a more convenient hypothesis, not more power.
▸
Every integer $\ge 2$ is a product of primes: split a composite $k+1 = ab$ with $a, b \in [2, k]$ , then apply the strong IH to both factors.
▸
Well-Ordering Principle (WOP): every nonempty subset of $\mathbb{N}$ has a least element. Special to $\mathbb{N}$ (fails for $\mathbb{Q}^+$ and $\mathbb{Z}$ ), and equivalent to induction.
▸
Smallest-counterexample (minimal criminal) proofs: assume a counterexample exists, take the least one by WOP, break it with an even smaller one — a flavor of proof by contradiction.