One idea, one pictureClaim: every postage of 8 cents or more can be paid with 3-cent and 5-cent stamps. Click some dominoes to make them starting dominoes, then press “Push!”. What is the fewest starting dominoes that knock down everything from 8 on?
Loading figure…
In one sentence
Let P(n) be a statement about positive integers n, and k a fixed positive integer. If
P(1),P(2),…,P(k) all hold, and
P(n) implies P(n+k),
then P(n) holds for every positive integer n. k is called the step size; k=1 is the first principle of induction.
A bigger step size allows a bigger “move” in each step: add a 3-cent stamp at once, cut one piece into 4 at once. The price is more base cases: each base case only looks after the chain of numbers with the same remainder on division by k.
Example: every postage of 8 cents or more can be paid with 3-cent and 5-cent stamps
Step 1 / 6
Loading figure…
Choose the step size
If you can pay n cents, one more 3-cent stamp pays n+3 cents. So choose step size k=3: P(n)⇒P(n+3).
P(n)⇒P(n+3)
Only one base
Two bases
Three bases
Bases cannot be picked at will
A different step size
Predict first
With 3-cent and 5-cent stamps, what is the largest postage that cannot 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.
1,2,4,7 cents cannot be paid, while 8,9,10 can, so by induction with step size 3 everything from 8 cents on can be paid. The largest is 7 cents.
In general, for coprime values a,b, the largest amount that cannot be paid is ab−a−b. Here 15−3−5=7.
Stop 1 · Number theory: a different pair of stamps
Now the stamps are 4 cents and 7 cents. First guess where “everything can be paid” starts, then check it with step size 4: click 4 consecutive bases.
Loading figure…
Can 17 be a base? Also try step size 7: how many bases do you need?
18=7+7+4, 19=7+4+4+4, 20=4×5, 21=7×3; together with “add one 4-cent stamp”, everything from 18 on can be paid. But 17 cannot (17,13,9,5,1 are not multiples of 7).
Stop 2 · Geometry: cutting a square into n squares
Claim For n≥6, a square can be cut into n squares (not necessarily of the same size).
The most natural move here: cut one of the small squares into 4 with a cross — that adds 3 squares. So the step size is 3.
Dissection with step size 3
Step 1 / 5
The inductive step
If a square can be cut into n squares, cut one of them into 4 with a cross: that gives n+3.
P(n)⇒P(n+3)
Base n = 6
Base n = 7
Base n = 8
Three chains together
Loading figure…
Here the bases are not checked automatically — you have already seen the dissections for 6,7,8 above. Click only 6 and 8: which chain stays standing?
Stop 3 · Sums: two terms at a time
Find Sn=−12+22−32+42−⋯+(−1)nn2.
Inducting one term at a time, the sign of each step flips back and forth, so you have to split into odd and even. Better to take two steps at once: two neighboring terms −(m)2+(m+1)2 always have the same sign pattern.
The algebra is actually not hard — the sign (−1)n stays outside throughout. The hard part is “thinking of taking it out”.
CostIt works, but every step must deal with the parity of n.
Step size 2: terms in pairs
Bases: S1=−1=(−1)1⋅21⋅2, S2=−1+4=3=22⋅3.
Inductive step: the two added terms are (−1)n+1(n+1)2+(−1)n+2(n+2)2=(−1)n[(n+2)2−(n+1)2]=(−1)n(2n+3), so
Sn+2=(−1)n[2n(n+1)+2n+3]=(−1)n+22(n+2)(n+3).
CostTwo bases to check, but every step adds a difference with the same sign.
Induction with step size k really splits the statement into k groups by the remainder on division by k, and does ordinary induction once in each group.
Practice
Exercise 1Basic
Using only 4-cent and 5-cent stamps, what is the largest postage that cannot be paid?
Hint · direction
Try from small to large: which amounts can be paid? What happens after 4 in a row can be paid?
Hint · method
Take step size 4 (add one 4-cent stamp). Find 4 consecutive amounts that can be paid; everything after them can be paid too.
Hint · first step
12=4⋅3, 13=4⋅2+5, 14=4+5⋅2, 15=5⋅3.
Full solution
12,13,14,15 can all be paid, so by induction with step size 4, every n≥12 can be paid. But 11 cannot (11,7,3 are not multiples of 5; 11−5=6 and 11−10=1 are not multiples of 4 either). The answer is 11 (=4×5−4−5).
Exercise 2Basic
You prove the claim of Stop 2 by induction whose step is “cut one square into 4 with a cross”. Which values of n must you check by hand as base cases? (Separate them with commas.)
Hint · direction
Each cross cut increases the number of squares by how many?
Hint · method
The step size is 3, so you need 3 consecutive bases. From which n does the claim start?
Hint · first step
The claim is for n≥6: count 3 values starting from 6.
Full solution
6,7,8.
Exercise 3Advanced
A statement P(n) satisfies P(n)⇒P(n+5), and P(3),P(4),P(6),P(7) hold. For how many n with 3≤n≤30 does P(n)not follow from this?
Hint · direction
Each base starts a chain: 3,8,13,…. Which chain has no base?
Hint · method
Group by remainder on division by 5: 3,4,6,7 have remainders 3,4,1,2. Which remainder is missing?
Hint · first step
Remainder 0 is missing: the chain 5,10,15,… has no base. Each of the other four bases is the first number of its chain with n≥3.
Full solution
What does not follow is exactly the multiples of 5 with 3≤n≤30: 5,10,15,20,25,30, that is 6 values. Check P(5) as well and that chain falls too.
Exercise 4Challenge
Prove that for n≥6, an equilateral triangle can be cut into n equilateral triangles.
Hint · direction
Which move increases the number of equilateral triangles by a fixed amount?
Hint · method
Joining the midpoints of the sides of an equilateral triangle turns it into 4 equilateral triangles: 3 more. Step size 3, so check the bases 6,7,8.
Hint · first step
7: cut into four, then cut one of those into four: 3+4=7. For 6 and 8, “subdivide, then merge” as with the square.
Full solution
Divide each side into 3 equal parts to get 9 small equilateral triangles, and merge the side-2 triangle in one corner (made of 4 small ones) into one: 9−4+1=6. Divide each side into 4 parts to get 16, and merge the side-3 triangle in one corner (made of 9 small ones): 16−9+1=8. 7 is in the previous hint. Then, by “cut one of them into four”, P(n)⇒P(n+3), so it holds for every n≥6.
The wrong step: We want P(n) for every n≥1. We checked P(1) and proved P(n)⇒P(n+2), so the statement holds.
What went wrong? Think first, then open
DiagnosisP(1) knocks over P(3), P(3) knocks over P(5), … only the odd numbers fall. Nobody pushes P(2), so not one domino in the even chain falls.
✓
The right step: With step size k you must check k consecutive base cases P(1),…,P(k). Each base starts one chain, and together they cover every remainder on division by k.
“Step size k means k base cases”
Exhibit
A “convenient” step size whose step does not actually work
✗
The wrong step: If n cents can be paid, so can n+1 cents (n≥8): just pay 1 cent more.
What went wrong? Think first, then open
DiagnosisThere are only 3-cent and 5-cent stamps, no 1-cent ones. The inductive step must really be doable: from a way of paying n, build a way of paying n+1.
✓
The right step: Either change the step size — add one 3-cent stamp, n⇒n+3 — or do step size 1 properly: if the payment uses a 5, swap one 5 for two 3s; if it has no 5 (so at least three 3s), swap three 3s for two 5s.
“Choose the step size so that the step really works”
Choosing the Right Step Size ← → step · F full screen · Esc exit