Discrete Math · Undergraduate
Strong Induction and the Well-Ordering Principle
Quick answer
Ordinary induction assumes one case, P(k), to prove the next. Strong induction assumes every case from the start up to k. That extra strength is what you need when a case leans on values further back: factoring a number into primes uses its factors, and the Fibonacci recurrence uses the two previous terms. A step that reaches back several places needs that many base cases. Strong induction matches the well-ordering principle: every nonempty set of positive integers has a least element.
What you'll learn
- State the principle of strong induction
- Decide how many base cases a proof needs
- Prove results about prime factorizations, postage and recurrences
- Connect strong induction with the well-ordering principle
Assuming everything so far
Ordinary induction proves from alone. Sometimes the next case depends on an earlier one instead. Strong induction lets you assume all of them:
- Base cases. Prove , and as many following cases as the step needs.
- Step. Assume are all true, and prove .
Then holds for every .
Why the extra assumption is allowed
Imagine the cases as dominoes. In ordinary induction each domino knocks over the next. In strong induction, by the time domino is reached, every earlier domino has already fallen, so leaning on any of them is fair. Nothing new is being assumed; strong induction only admits that the earlier cases were proved too. Equivalently, if some failed, there would be a smallest failure by the well-ordering principle, and the step would show that smallest failure is not one: a contradiction.
Worked examples
Common mistakes
Practice problems
-
Prove that every amount of cents or more can be paid with - and -cent stamps. Which base cases are needed?
Answer
, and
Full solution
, , . The step adds a -cent stamp to , which reaches back places.
-
Which amounts cannot be paid with - and -cent stamps?
Answer
Full solution
Every amount from on works, by Example 2; checking the smaller amounts by hand leaves these six.
-
With , and , find , and .
Answer
, ,
Full solution
, , .
-
Prove that the sequence in Exercise 3 satisfies .
Answer
Check , then substitute the formula for and .
Full solution
.
-
A chocolate bar has squares. Each break splits one piece into two. Prove it takes breaks to separate all squares.
Answer
After the first break into pieces of and squares, they need more.
Full solution
Base: needs breaks. Step: , using the assumption for .
-
How many base cases does a proof need if its step uses and ?
Answer
Full solution
The step for uses , three places back, so the first three cases must be checked directly.
-
Use well-ordering to explain why there is no smallest positive rational number.
Answer
Well-ordering applies to integers only; for any positive rational , is smaller.
Full solution
The positive rationals are not well-ordered, which is why induction is a tool for integers.
-
A student proves checking only . What is wrong?
Answer
The step uses two earlier terms, so must be checked too.
Full solution
For , the step would need , which is outside the proof’s range.
Frequently asked questions
What is strong induction?
To prove P(n) for all n ≥ n₀: prove the base case(s), then show that if P(n₀), …, P(k) are all true, P(k + 1) is true.
When do you need strong induction?
When proving P(k + 1) needs a case other than P(k), such as P(k − 1), P(k − 3) or P(a) for a factor a of k + 1.
How many base cases are needed?
Enough that the step never reaches below them. If the step uses P(k − 3), the first four cases must be checked directly.
Is strong induction stronger than ordinary induction?
No. Each can be derived from the other; strong induction is ordinary induction applied to 'P holds for every case up to n'.
What is the well-ordering principle?
Every nonempty set of positive integers has a smallest element. Proofs by smallest counterexample use it.