A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Strong induction (complete induction) assumes P(k) for all k ≤ n when proving P(n+1), providing more flexibility than regular induction. The well-ordering principle—every non-empty subset of ℕ has a minimum element—is logically equivalent to induction and provides an alternative proof method. These techniques are essential for proofs involving recursion or sequences with complex dependencies.
From mathematical induction, you know the standard structure: prove P(1), then prove that P(n) implies P(n+1), and conclude P holds for all natural numbers. This works when each case depends only on the immediately preceding one. But many situations are messier. To prove that every integer n ≥ 2 can be written as a product of primes, the inductive step looks like this: if n+1 is prime, it is already a product; if n+1 is composite, it factors as a·b where 2 ≤ a, b < n+1. The inductive hypothesis needs to apply to *both* a and b, not just to n. Standard induction's "assume P(n), prove P(n+1)" cannot reach back to arbitrary smaller values.
Strong induction (also called complete induction) solves this by strengthening the inductive hypothesis. Instead of assuming only P(n), you assume P(k) holds for *all* k with 1 ≤ k ≤ n, then prove P(n+1). The base case is the same (prove P(1)), but now in the inductive step you have the entire history of the statement up through n at your disposal, not just the last step. Strong induction is logically equivalent to ordinary induction — neither is more powerful in what it can ultimately prove — but it is often dramatically more convenient when each case depends on multiple earlier cases. Fibonacci numbers, recursive algorithms, and the Fundamental Theorem of Arithmetic are classic examples where the reach-back is natural and unavoidable.
The well-ordering principle states that every non-empty subset of the natural numbers contains a least element. This sounds obvious — of course {3, 7, 11} has a minimum — but it is a genuine axiom, not provable from basic arithmetic without it. The well-ordering principle provides an alternative proof method: to prove P(n) for all n ∈ ℕ, assume for contradiction that there exists some n where P(n) fails. The set of counterexamples is non-empty, so by well-ordering it has a minimum element n₀. You then derive a contradiction from the existence of a minimal counterexample, typically by constructing an even smaller counterexample or showing P(n₀) must hold after all.
The two methods — strong induction and well-ordering — are logically equivalent; each can be derived from the other. Well-ordering proofs are often more natural when you want to argue about a "first" failure, while strong induction is cleaner when building a sequence step by step. A good instinct: if your proof says "suppose n₀ is the smallest counterexample," you are implicitly using well-ordering. If it says "assume P(k) for all k < n, then prove P(n)," you are using strong induction. Recognizing which framing fits your argument is a key skill in mathematical proof-writing.
One important note on the base case: with strong induction, you sometimes need to establish multiple base cases before the inductive step becomes valid. For example, a statement about Fibonacci numbers F(n) might need both F(1) and F(2) as base cases because the recurrence F(n) = F(n−1) + F(n−2) requires two previous values. Always check that your inductive step's assumptions are actually satisfied at the boundary — the well-ordering and strong-induction frameworks guarantee nothing if the foundation is missing.