In strong induction you may assume every statement P(1),…,P(k) to prove P(k+1)
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
write a proof by strong induction with the right number of base cases;
use the well-ordering principle with a smallest counterexample;
choose between ordinary and strong induction.
When one step back is not enough
Every whole number n≥2 is a product of primes. Try to prove it by ordinary induction. Assume k is a product of primes. Does that tell us anything about k+1? No. The factors of k+1 have nothing to do with k. We need the smaller factors of k+1, which could be any numbers below it.
Strong induction
Let P(n) be a statement for each n≥n0. Suppose that:
P(n0) is true;
for every k≥n0, if P(n0),P(n0+1),…,P(k) are all true, then P(k+1) is true.
Then P(n) is true for every n≥n0. The difference from ordinary induction is in the hypothesis: we may use every earlier statement, not only the last one. It is also called complete induction.
Prime factors. Let P(n) say that n is a product of primes, for n≥2. P(2) is true, since 2 is prime. Assume P(2),…,P(k). If k+1 is prime, we are done. If not, k+1=ab with 2≤a,b≤k. By the hypothesis, a and b are products of primes, so k+1 is one too.
Stamps and base cases
Stamps come in 3 units and 5 units. Which amounts can be paid exactly? The amounts 1, 2, 4 and 7 cannot. We claim that every amount n≥8 can.
Base cases.8=3+5, 9=3+3+3, 10=5+5.
Step. Let k+1≥11, and assume every amount from 8 to k can be paid. Then (k+1)−3≥8, so k−2 can be paid. Add one stamp of 3.
Conclusion. By strong induction, every amount n≥8 can be paid.
Why three base cases? The step goes back 3 places. With only the base case 8, the step from 8 would reach 11, 14, 17 and so on, and never 9 or 10. A step that goes back r places needs r base cases in a row.
A row of numbered boxes for the amounts 1 to 14. The boxes 1, 2, 4 and 7 are red with a cross, because those amounts cannot be paid with stamps of 3 and 5. Every other box is green with its stamps written under it, for example 8 = 3 + 5, 9 = 3 + 3 + 3 and 10 = 5 + 5. A bracket over 8, 9 and 10 is labelled base cases, and arrows from 8 to 11, 9 to 12 and 10 to 13 are labelled add a 3.
For any two values a and b with no common factor, the largest amount that cannot be paid is ab−a−b. With 3 and 5 that is 15−8=7, as we found.
The well-ordering principle
Every non-empty set of positive integers has a least element.
It sounds obvious. Yet it fails for other sets: the positive fractions have no least element, and neither do all the integers. It is the reason induction works, and it gives a second style of proof.
Proof by a smallest counterexample. Suppose a statement is false for some positive integers. Among those there is a least one, m. Now show that a smaller counterexample exists, or that m cannot be a counterexample. Either way we have a contradiction, so there is no counterexample at all.
Example. Every n≥2 has a prime divisor. Let D be the set of divisors of n that are bigger than 1. It contains n, so it is not empty, and it has a least element p. If p were not prime, it would have a divisor d with 1<d<p, and d would also divide n. Then d is in D and smaller than p, which is impossible. So p is prime.
Ordinary induction, strong induction and the well-ordering principle can each be proved from the others. Use the one that makes the argument shortest.
Practise with new numbers
Try it in Python
The program finds the amounts that cannot be paid with stamps of 3 and 5. Then it splits 360 into primes in the way the strong induction proof does.
Common mistakes
Too few base cases. If the step uses P(k−2), you need three base cases in a row.
A step that reaches below the base. The stamp step uses k−2, which must be at least 8.
Thinking strong induction is a different truth. It proves the same things. It only lets the hypothesis say more.
Forgetting that the least element must exist. The well-ordering principle needs a non-empty set of positive integers.
. It handles results that look back more than one step, such as prime factors and stamp amounts. A step that looks back
r
places needs
r
base cases. The well-ordering principle, that every non-empty set of positive integers has a least element, is the same idea, used through a smallest counterexample.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself
This lesson is free to read. Enroll free to keep your place and take the tests.