1
The hypothesis covers everything below k+1
You may use any of P(n₀) through P(k), and you need not know in advance which.
Lesson · Induction and Recursion · Induction
Strong Induction
When P(k+1) depends on cases further back than P(k), ordinary induction gives you the wrong hypothesis. Strong induction assumes all of P(n₀), …, P(k) and is exactly as valid.
ordinary: P(k) ⟹ P(k+1)
strong: P(n₀)…P(k) ⟹ P(k+1)
Same power. Strong induction proves nothing ordinary cannot.
Use it when the step reaches back an unknown distance.
A stronger hypothesis, the same theorem
Core ideas
What this lesson establishes
Strong induction is not a stronger technique. It is a more convenient hypothesis for claims whose step does not reach back exactly one step.
2
It is equivalent to ordinary induction
Apply ordinary induction to Q(n) = "P(m) holds for all n₀ ≤ m ≤ n" and strong induction falls out. Neither proves more than the other.
3
Multiple base cases are often needed
If the step reaches back two places, two base cases are required — otherwise the step at k+1 = n₀+1 has nothing to stand on.
The material
Strong induction
Statement, the two standard applications, and the base-case trap.
Theorem · Strong induction
Let P(n) be a statement about n ≥ n₀. If P(n₀) holds and, for every k ≥ n₀, the truth of P(n₀), …, P(k) implies P(k+1), then P(n) holds for all n ≥ n₀.
Nothing is gained in strength. Define Q(n) to be "P(m) holds for all n₀ ≤ m ≤ n". Ordinary induction applied to Q gives exactly strong induction for P. What is gained is a hypothesis that matches the shape of certain arguments.
Theorem · Every integer n ≥ 2 is a product of primes
Every integer greater than 1 can be written as a product of one or more primes.
Base. 2 is prime, so it is a product of one prime.
Step. Let k ≥ 2 and assume every integer from 2 to k is a product of primes. Consider k+1.
If k+1 is prime, it is a product of one prime and we are done. Otherwise k+1 = ab with 2 ≤ a, b ≤ k. By the strong hypothesis both a and b are products of primes, so their product k+1 is too.
□
Ordinary induction is useless here. Knowing that k factors says nothing about k+1, and the factors a and b could be anywhere below k+1. The hypothesis has to cover them all, and only strong induction provides that.
Multiple base cases
Theorem · Every amount of postage n ≥ 8 can be made from 3¢ and 5¢ stamps
For every n ≥ 8 there are non-negative integers a, b with n = 3a + 5b.
Bases. 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5. Three base cases are needed because the step reaches back three places.
Step. Let k ≥ 10 and assume the claim for every value from 8 to k. Then k + 1 − 3 = k − 2 ≥ 8, so by the hypothesis k − 2 is expressible; adding one 3¢ stamp expresses k+1.
□
Three base cases, because the step goes back three. Providing only n = 8 would leave the step at k+1 = 9 and k+1 = 10 appealing to 6 and 7, which are outside the claim — and indeed 7 cannot be made at all. Counting the base cases correctly is the whole difficulty of this style of proof.
Strong induction and recursion
Strong induction is the natural partner of a recursive definition whose recursive calls are not on n − 1. Merge sort splits at n/2; binary search halves; the Fibonacci recurrence reaches back two. In every case the correctness proof needs a hypothesis covering all smaller values, which is what “Recursive Algorithms and Correctness” does.
Example · Fibonacci and strong induction
Proving a property of Fₙ = Fₙ₋₁ + Fₙ₋₂ requires both Fₙ₋₁ and Fₙ₋₂, so it needs two base cases and a hypothesis covering two steps back. Attempting it with ordinary induction leaves Fₙ₋₂ unavailable.
Interactive
Check P(n), then notice checking is not proving
Two of these statements are false
Method
Writing a strong induction proof
Count how far the step reaches, then supply that many base cases.
1
Decide whether ordinary induction suffices
If P(k+1) follows from P(k) alone, use ordinary induction. Reaching for the stronger hypothesis unnecessarily obscures what the proof used.
2
State the strong hypothesis explicitly
"Assume P(m) for every m with n₀ ≤ m ≤ k." Writing it out is what keeps you from using a case outside the range.
3
Count how far back the step reaches
The postage step used k − 2, three places back, so three base cases were needed. Miscounting here is the standard error.
4
Verify every base case
Each one individually. A base case you assumed rather than checked is a hole at exactly the place the step cannot cover.
Strong induction
Score 0 / 0Choose the answer you can justify.
Every n ≥ 12 is 4a + 5b for non-negative integers
The step will reach back four, so four base cases are needed.
BASES 12 = 4+4+4 13 = 4+4+5 14 = 4+5+5 15 = 5+5+5
STEP Let k ≥ 15 and assume the claim for every m with 12 ≤ m ≤ k.
k + 1 − 4 = k − 3 ≥ 12,
so k − 3 = 4a + 5b by the hypothesis,
and k + 1 = 4(a+1) + 5b.
CONCLUDE Every n ≥ 12 is expressible. ∎
Why four bases: the step covers k+1 ≥ 16 only.
12 through 15 are not reached by it and must be checked.
The largest amount that cannot be made from 4 and 5 is 11, which is the Frobenius number of the pair. For coprime a and b it is always ab − a − b, here 20 − 4 − 5 = 11 — which is why the claim starts at 12 and not somewhere else.
Common mistakes
1
Supplying one base case when the step reaches back severalThe number of base cases must cover every value the step cannot reach. This is the single most common error in strong induction proofs.
2
Using a case outside the hypothesis rangeThe hypothesis covers n₀ to k. Appealing to P(k+2) or to P(n₀ − 1) is using something you have not got.
3
Reaching for strong induction by defaultIf the step uses only P(k), say so. Stating a stronger hypothesis than the proof needs hides what the argument actually depends on.
Check your understanding
✓
Finish when you can count the base cases from the step.
Prove that every n ≥ 18 can be made from 4¢ and 7¢ stamps. Work out how far back your step reaches before writing any base case, and check that the number of bases matches.
Note: The equivalence of ordinary induction, strong induction and well-ordering means a proof by one can always be rewritten as a proof by another. Which reads best depends entirely on the claim, and choosing well is a matter of exposition rather than correctness.