Strong Induction

Strong induction is the workhorse behind unique factorization and its generalizations in algebra (existence of factorizations in any Noetherian ring, existence of prime factorizations in principal ideal domains). In combinatorics, it justifies formulas for recursively defined sequences and structures where the recursion is not a simple shift, such as recurrences $a_n$ depending on several or all previous terms (partition numbers, Catalan-type recursions, dynamic programming recurrences). In computer science, strong induction is the standard tool for proving correctness and termination of recursive algorithms that divide a problem into pieces of varying smaller sizes — merge sort, quicksort, binary search trees, and any divide-and-conquer algorithm — as well as for structural induction on recursively defined data types like trees and terms in a formal grammar, where a node's children can be of arbitrary smaller "size." In mathematical logic, strong induction underlies proofs by induction on the complexity of well-formed formulas and derivations in formal proof systems, where a compound formula's immediate subformulas are of strictly smaller complexity but not related by a "minus one" pattern. In cryptography and algorithm analysis, strong induction justifies correctness proofs of recursive number-theoretic algorithms such as the extended Euclidean algorithm and fast modular exponentiation. It also connects directly forward to the Well-Ordering Principle: proofs "by minimal counterexample," ubiquitous in advanced number theory and combinatorics, are a stylistic variant of strong induction, and the equivalence between the two is itself a standard exercise built on the machinery developed here.

:::quiz[In the strong inductive step "$\forall n \ge n_0,\ [\forall k\,(n_0 \le k < n \Rightarrow P(k))] \Rightarrow P(n)$", what happens when $n = n_0$?]

• The step is undefined at $n_0$ and must be excluded
• The antecedent is vacuously true, so the step forces $P(n_0)$ to hold outright ✓
• The antecedent is always false at $n_0$, so nothing is proved
• $P(n_0)$ must be assumed separately and cannot come from the step

Ask the tutor: Can you show me why "proof by minimal counterexample" using the Well-Ordering Principle is logically the same technique as strong induction?

Ordinary induction is a line of dominoes: knocking over domino $n$ knocks over domino $n+1$, so one push starting the chain topples everything. Strong induction is better pictured as a wall being built course by course, where laying brick $n$ is allowed to rest on any combination of bricks already laid — not only the brick directly beneath it. This matters when the "natural" decomposition of $n$ does not point at $n - 1$ at all. Factoring $12 = 3 \times 4$ points at $3$ and $4$, both far below $11$; a recursive algorithm computing Fibonacci-like sequences with a jump, or parsing a syntax tree, routinely needs to reach back to an arbitrary earlier stage, not merely the previous one. The key logical fact — proved in the theorem below — is that this apparent extra power is an illusion at the level of what can be proved: strong induction is derivable from ordinary induction by a simple trick, running ordinary induction not on $P$ itself but on the auxiliary statement "$P$ holds for every value up to and including $n$." The strength gained is purely one of bookkeeping convenience: you get to reach for whichever earlier case you like, instead of being forced to relate $n$ only to $n-1$.

Example 1: Every integer $n \ge 2$ is a product of (one or more) primes. Here "product of primes" includes the degenerate case of a single prime (a product of one factor). We prove this by strong induction with $n_0 = 2$. Setup. Let $P(n)$ be the statement "$n$ is a product of primes," for $n \ge 2$. Strong inductive step. Fix $n \ge 2$ and suppose, as the strong inductive hypothesis, that $P(k)$ holds for every integer $k$ with $2 \le k < n$. We must show $P(n)$. Case A: $n$ is prime. Then $n$ is trivially a product of one prime (itself), so $P(n)$ holds. Case B: $n$ is not prime. Since $n \ge 2$ and $n$ is not prime, by definition of "prime" there exist integers $a, b$ with $n = ab$ and $1 < a < n$, $1 < b < n$. (This uses the standard definition: an integer $\ge 2$ that is not prime has a nontrivial factorization; a full justification of why a non-prime $\ge 2$ has such $a,b$ is a short separate argument — take $a$ to be the smallest divisor of $n$ exceeding $1$, and $b = n/a$ — but we take it as known here as it is not the inductive content.) Since $1 < a < n$ and $1 < b < n$, both $a$ and $b$ lie in the range $2 \le k < n$. By the strong inductive hypothesis, $P(a)$ and $P(b)$ both hold: $a = p_1 p_2 \cdots p_r$ and $b = q_1 q_2 \cdots q_s$ for primes $p_i, q_j$. Then

a product of primes. So $P(n)$ holds in this case too. In both cases $P(n)$ holds, establishing the strong inductive step for all $n \ge 2$. (Note that at $n=2$, the hypothesis "$P(k)$ for $2 \le k < 2$" is vacuous, and Case A applies since $2$ is prime — this is exactly the base case being absorbed into the general step, as guaranteed by the theorem.) By strong induction, $P(n)$ holds for all $n \ge 2$: every integer $n \ge 2$ is a product of primes. $\blacksquare$ This example is the paradigm case for strong induction: the factor $a$ could be any number strictly between $1$ and $n$ — for instance if $n = 91 = 7 \times 13$, the inductive step needs $P(7)$ and $P(13)$, neither of which is $P(90)$. Ordinary induction, which only ever hands you $P(n-1) = P(90)$, is structurally the wrong tool: knowing $90$ factors into primes tells you nothing about how $91$ factors.

Example 2: The "postage stamp" problem — every integer $n \ge 8$ can be written as $n = 3a + 5b$ with $a, b \in \mathbb{Z}_{\ge 0}$. This models: using only $3$-cent and $5$-cent stamps, every postage amount from $8$ cents up is achievable. Setup. Let $P(n)$: "$\exists a, b \in \mathbb{Z}_{\ge 0}$ with $n = 3a + 5b$," for $n \ge 8$. Base cases (checked directly, three of them, since the recursive step below will reach back up to three steps).

• $n = 8$: $8 = 3(1) + 5(1)$. ✓
• $n = 9$: $9 = 3(3) + 5(0)$. ✓
• $n = 10$: $10 = 3(0) + 5(2)$. ✓

Strong inductive step. Let $n \ge 11$ and suppose $P(k)$ holds for every $k$ with $8 \le k < n$ — in particular, since $n \ge 11$, the value $k = n - 3$ satisfies $8 \le n-3 < n$, so the strong inductive hypothesis applies to it: $P(n-3)$ holds. Thus there exist $a', b' \ge 0$ with

Then

with $a' + 1 \ge 1 \ge 0$ and $b' \ge 0$, so $P(n)$ holds. By strong induction (with the three base cases $8,9,10$ handled directly, covering all residues mod $3$, and the step for $n \ge 11$ reaching back exactly $3$), $P(n)$ holds for all $n \ge 8$. $\blacksquare$ This example illustrates a second common pattern: the inductive step reaches back a fixed distance ($3$, not $1$), so more than one base case is required — precisely as many base cases as the reach, here three consecutive values $8, 9, 10$, so that every larger $n$ can be reduced by repeated subtraction of $3$ down into the base range. This is a case where the strong inductive step technically only needs one specific earlier value ($P(n-3)$), yet is naturally phrased using the full strength of strong induction because "one step back" (ordinary induction) does not align with the recursion at all.