Ordinary induction proves from alone. Many natural statements do not work this way. A composite number factors into two smaller numbers that are not necessarily ; a recursively defined sequence may depend on two or more earlier terms. This unit proves strong induction from the well-ordering principle and shows how to use it, together with the equivalent method of the minimal counterexample. It builds on the discussion of proof architecture and ordinary induction in unit 1.2.
The well-ordering principle
Definition 1.4.1
(Well-ordering principle)
Let . The well-ordering principle states: every nonempty subset has a least element, that is, an element with for all . The same holds for every nonempty set of integers that is bounded below, by shifting.
The principle fails for (no least element in itself) and for the positive reals (the set has no least element).
Counterexample mode
Well-ordering fails outside the natural numbers
Claim: every nonempty set of positive rationals has a least element. Take . It is nonempty, and for any member the member is strictly smaller, since gives . So no member of is least. The claim is false for ; the repair is to keep the hypothesis that the set consists of integers bounded below, which is exactly what the principle assumes.
Strong induction
Theorem 1.4.2
(Strong induction)
Let be an integer and let be a statement for each integer . Suppose that for every integer the following implication holds:
Then is true for every integer .
Proof
(Take the least failure)
Suppose not. The set is nonempty and bounded below, so it has a least element . By minimality of , is true for every with . The hypothesis of the theorem then gives , contradicting .
Proof X-ray
Why no separate base case appears
The proof uses well-ordering exactly once, to choose the least element of the failure set, and uses the induction hypothesis exactly once, at that least element. Minimality supplies the whole premise at once: every smaller index is outside , so holds for all of them. This is the reason strong induction needs no explicit base case. For the premise " for all " ranges over no indices and is vacuously true, so the implication at asserts outright. The proof does not say how to prove that implication, which is where the real work and the practical base cases appear. Boundedness below is essential: without it need not have a least element, and the argument has nothing to select.
Two remarks. First, in practice the first few cases are proved separately, because the general step typically needs at least one earlier case to refer to. Second, ordinary induction is the special case in which the step uses only .
A proof by strong induction therefore has this shape: fix , assume for all earlier , and prove . When the argument refers to specific earlier cases such as or , one must check that those indices are at least , which is why several base cases are needed.
The minimal counterexample method
The proof of strong induction can be used directly. To prove , assume the set of counterexamples is nonempty, take its least element , and derive a contradiction from the fact that every smaller index satisfies . This is logically identical to strong induction; choose whichever reads more clearly.
Worked examples
Worked example 1.4.3
(Prime factorization exists)
Every integer is a product of one or more primes. We use strong induction with . Let and assume the claim for all with . If is prime, it is a product of one prime. Otherwise with . By the hypothesis, and are products of primes, so is as well.
Note that the argument uses the hypothesis for two different earlier values and , neither of which is determined in advance as .
Worked example 1.4.4
(Stamps of value four and five)
Every integer can be written as with integers . The step refers to , which is at least only when , so we prove four base cases: , , , . Now let and assume the claim for all with . Since and , we have with , so .
Worked example 1.4.5
(Binary representation exists)
Every integer is a sum of distinct powers of . Take and assume the claim for all . If , then . If , let be the largest power of with , so . If we are done. Otherwise satisfies because . By hypothesis is a sum of distinct powers of , and each of them is at most , so none equals . Adding gives the required representation of .
Worked example 1.4.6
(A recursive sequence)
Define , , and for . The first terms are . Claim: for all . Two base cases are needed: and . Let and assume the formula for and . Using and ,
The edge case is the first index , where the step reaches back to both base cases at once.
Common mistakes and subtle points
Common mistake
(Too few base cases)
If the step refers to , then already refers to , which is outside the range. Both and must be established separately. In the stamps example the step refers to , which forces four base cases.
Common mistake
(Using the hypothesis at n or outside the range)
In the inductive step we may use only for , never itself. The indices must also lie in the allowed range: in the factorization example the decomposition must satisfy for the hypothesis to apply to both factors.
Common mistake
(Minimal counterexamples outside a well-ordered set)
The minimal counterexample argument applies to subsets of or of the integers bounded below, not to subsets of : a set of counterexamples such as has no least element. If the step only needs , ordinary induction is clearer.
Exercises
Quick check
(Show that is an integer for every by deducing it from the recurrence in the sequence example.)
Prove by strong induction that the recurrence produces integers.
Solution · Guided solution
Define by the recurrence , , . By strong induction on we show : the base cases and are integers, and for the integers give the integer . Since the closed form equals by the sequence example, is an integer for every . (For instance gives .)
Quick check
(Prove that every integer can be written as with integers .)
The step reaches back places, so decide how many base cases are needed.
Solution · Guided solution
Base cases: , , . Let and assume the claim for all with . Since and , we have with , so . Three base cases are needed because the step reaches back places.
Quick check
(Let and for . Prove that for all .)
Two base cases, then bound by the two earlier bounds.
Solution · Guided solution
Base cases: and . Let and assume for all . Then
Quick check
(Use the well-ordering principle to prove that there is no integer with .)
Assume the set of such integers is nonempty and look at its least element .
Solution · Guided solution
Suppose the set of integers with were nonempty. Then and has a least element . Since , multiplying the inequality by the positive number gives , and . Also . So is an integer with , that is , and contradicts the minimality of . Hence is empty.