One idea, one pictureYou only have 3-cent and 5-cent stamps. Click cells to make some amounts hand-checked base cases, so that everything from some point on lights up. What is the smallest number of bases you need?
Loading figure…
In one sentence
The second principle of mathematical induction (strong induction):
Base case: P(1) is true;
Inductive step: assuming P(1),P(2),…,P(k) are all true, prove that P(k+1) is true.
Then P(n) holds for every positive integer n.
It is really the same thing as the first principle: let Q(n) be the statement “P(1),…,P(n) are all true” and apply the first principle to Q(n). The only difference is how it feels to use: to knock over the next domino, you may use any of the earlier ones, not only the one right before it. But be careful: if P(k+1) uses P(k−2), then P(1),P(2),P(3) all need their own base case. The grid below shows you why.
Example: 3-cent and 5-cent stamps pay any amount of 8 cents or more
Step 1 / 5
Loading figure…
The recursive link
If you can pay n−3 cents, add one 3-cent stamp and you can pay n cents. So P(n) follows from P(n−3): the step looks back three cells, not one. The cells are laid out in 3 columns, so n−3 sits right above n.
P(n)⇐P(n−3)
One base is not enough
One for each of the three columns
Written as strong induction
Why 7 does not work
Predict first
You only have 4-cent and 7-cent stamps. From which amount on can every amount be paid?
cents
Choose an answer first; then you can see the result.
✓You predicted it!✗Not what you expected — which is exactly why it is worth a pause.
The largest amount that cannot be paid is 17, so everything from 18 on works. 18=4+7+7, 19=4⋅3+7, 20=4⋅5, 21=7⋅3. This time the step is P(n)⇐P(n−4), so you need four consecutive base cases.
Loading figure…
Four columns, one base case in each. Turn on “Check each case” to see which amounts cannot be paid.
In general, when a and b are coprime, the largest amount that cannot be paid is ab−a−b (3⋅5−3−5=7, 4⋅7−4−7=17). This fact itself can also be checked with the method of this stop.
Stop 1 · Algebra: each term needs the two before it
If x+x1 is an integer, prove that xn+xn1 is an integer for every positive integer n.
Write sn=xn+x−n. You cannot get sk+1 from sk alone, but the identity below uses both sk and sk−1:
Example: x + 1/x is an integer
Step 1 / 4
Find the link
Multiply sk by s1, and an extra sk−1 appears.
sk⋅s1=xk+1+x−(k+1)+xk−1+x−(k−1)=sk+1+sk−1
The recurrence
Two base cases
Inductive step
Stop 2 · Number theory: jumping far back
Every integer greater than 1 can be written as a product of primes.
Here P(n) does not use P(n−1). It uses “some two numbers smaller than n”, and we do not know in advance which two. This is exactly what strong induction is for.
Example: every integer has a prime factorization
Step 1 / 4
Base case
n=2 is prime, so it is itself a product of primes (with one factor).
2=2
Assume every smaller case
Two cases
Why the first principle is not enough
If only one base case is checked
Break it
Counterexample lab: remove one condition
Conclusion: an=2n+1 for every n← still true?
a1=3,a2=5,an=3an−1−2an−2. Inductive step: if ak−1=2k−1+1 and ak=2k+1, then ak+1=3⋅2k+3−2k−2=2k+1+1. Both base cases are already set.
Loading figure…
Keep only the base case P(1). Click cell 2 to remove it and see what is left.
Loading figure…
Not a single cell follows: P(3) needs P(1)andP(2), and P(2) has nothing to stand on. P(2) itself would need P(1) and P(0), and P(0) is not even part of the problem. If each step looks back two cells, you must have two consecutive base cases.
Practice
Exercise 1Basic
You only have 5-cent and 7-cent stamps. What is the largest amount (in cents) that cannot be paid?
Hint · direction
First find 5 consecutive amounts that can all be paid; after that, every amount can be paid. (Why 5?)
Hint · method
The step is P(n)⇐P(n−5), so you need five consecutive base cases. Then check the amount just below them.
Hint · first step
24=5⋅2+7⋅2, 25=5⋅5, 26=5+7⋅3, 27=5⋅4+7, 28=7⋅4.
Full solution
All of 24 to 28 can be paid, so every amount from 24 on can be paid. 23−7y takes the values 23,16,9,2, none of which is a multiple of 5, so 23 cannot be paid. The answer is 23 (which also equals 5⋅7−5−7).
Exercise 2Basic
The sequence a1=1,a2=3,an=an−1+2an−2(n≥3). Find a6, and prove by strong induction that an≤2n.
Hint · direction
Work out the first few terms. In the proof, which two terms does ak+1 use?
Hint · method
Check two base cases, n=1,2. In the step, assume ak−1≤2k−1 and ak≤2k.
Hint · first step
a3=5, a4=11, a5=21.
Full solution
a6=21+2⋅11=43≤64. Proof: a1=1≤2 and a2=3≤4. If ak−1≤2k−1 and ak≤2k, then ak+1=ak+2ak−1≤2k+2⋅2k−1=2k+1.
Exercise 3Advanced
Prove that every positive integer is a sum of distinct powers of 2 (for example 13=8+4+1).
Hint · direction
To split up n, first take away the largest power of 2 you can. What is left is smaller than n.
Hint · method
Take 2m≤n<2m+1 and apply the induction hypothesis to n−2m (it can be any number smaller than n, so use strong induction).
Hint · first step
n−2m<2m+1−2m=2m, so 2m cannot appear again in the representation of n−2m.
Full solution
Base case: 1=20. Suppose every positive integer smaller than n works. If n is a power of 2, we are done. Otherwise take 2m<n<2m+1; then r=n−2m satisfies 1≤r<2m. By the induction hypothesis r is a sum of distinct powers of 2, each ≤r<2m, so after adding 2m the terms are still distinct.
Exercise 4Challenge
Given x+x1=3, find x5+x51.
Hint · direction
Use the recurrence from Stop 1. Do not solve for x.
The step uses two earlier terms, but only one base case is checked
✗
The wrong step: The sequence a1=3,a2=6,an=3an−1−2an−2. “Proof” that an=2n+1: for n=1, a1=3=2+1. Suppose ak−1=2k−1+1 and ak=2k+1. Then ak+1=3(2k+1)−2(2k−1+1)=2k+1+1.
What went wrong? Think first, then open
DiagnosisThe inductive step uses two earlier terms. The first time it can be used is for k+1=3, and then it needs P(1)andP(2). But P(2) was never checked. In fact a2=6=5, then a3=18−6=12=9, and the conclusion is wrong all the way.
✓
The right step: If the step uses several earlier terms, check that many base cases: here you must check both P(1) and P(2). As soon as you do, you find that P(2) is false.
“Look back as many cells as each step looks back”
The Second Principle of Induction ← → step · F full screen · Esc exit