Knock over the first domino, and make each one topple the next — they all fall.
Suppose you want to prove a statement about every positive integer at once — that 1 + 2 + ⋯ + n = n(n+1)2 holds for n = 1, for n = 100, for n = a billion, with no exceptions ever. You cannot check them one by one; there are infinitely many. Checking the first few is a trap — a pattern can hold for forty cases and then break on the forty-first. Mathematical induction is the tool that settles infinitely many cases with a single, finite argument. It works like a row of dominoes: knock over the first, guarantee each fallen one topples the next, and the whole line goes down. In this lesson we build that machine, run it on a sum and a divisibility claim, and learn the two traps that quietly break it — an inductive step that fails at even one link, and never using the assumption you were handed.
Patterns are seductive. Look at the function f(n) = n2 − n + 41. Plug in the positive integers and watch what comes out: 41, 43, 47, 53, 61, 71, … — every single one is a prime number. Keep going. It stays prime at n = 10, at n = 20, at n = 30, at n = 40 (where f(40) = 1601, prime). Forty cases in a row. Surely the rule "n2 − n + 41 is always prime" is true?
It is false. At n = 41 the spell breaks:
f(41) = 412 − 41 + 41 = 412 = 1681 = 41 × 41,
which is plainly not prime — you can see the factor of 41 the instant you write it as 412. Forty confirmations counted for nothing. A pattern is a conjecture, never a proof; no finite pile of examples can certify a claim about all of the infinitely many positive integers. We need an argument that reaches every n at once.
"It worked for the first few, so it's true" is not mathematics. Reading a rule off a handful of terms is the same mistake we met in 26.1: 2, 4, 8, … need not be 2n−1. To prove a statement holds for every positive integer, we need a method that covers all n — and induction is exactly that. It is the constructive cousin of proof by contradiction from Stage 16: both reach beyond "I checked some cases."
Stand an endless row of dominoes on a floor. You want to conclude that all of them fall. You do not have to push each one — that would take forever. Instead, secure two facts:
① The first domino falls.
② Whenever a domino falls, it knocks over the next one.
From these two facts alone, logic does the rest. The first falls (by ①). Because it fell, the second falls (by ②). Because the second fell, the third falls (by ② again). The chain never stops, so domino n falls for every n — no matter how far down the line you point. That is the whole principle of mathematical induction, dressed in wood.
Drag the slider to send the toppling wave down the row. Watch the fallen (green) dominoes overtake the standing (slate) ones — and read why every one of them must fall.
The power is in the chain. Fact ② is not "domino 5 falls" — it is "if a domino falls, then so does its neighbour," a single rule that applies at every position at once. Combine it with a starting push and the dominoes carry the conclusion to infinity for free. We never prove "n = 7 works" on its own; we prove the link and let it propagate.
Translate the dominoes into a proof template. Let P(n) be the statement you want to establish for every positive integer n. Induction asks for exactly two things:
① Base case. Show P(1) is true — check the statement directly at n = 1. This is "the first domino falls."
② Inductive step. Assume P(k) is true for some arbitrary positive integer k — this assumption is the inductive hypothesis — and use it to prove P(k+1) is true. This is "any fallen domino topples the next."
Once both are done, the principle of induction lets you conclude P(n) is true for all positive integers n. The base case lights the fuse; the inductive step guarantees it never goes out.
In the inductive step you are allowed to assume P(k) — that is the gift the previous domino hands you. You are not allowed to assume P(k+1); that is the very thing you must derive. The whole move is "P(k) ⇒ P(k+1)." If you find you never actually used the hypothesis P(k), the chain is broken and the proof is not valid.
Time to run the machine on real statements. We work the two-step method out loud, with no steps hidden.
Let P(n) be the claim Sn = 1 + 2 + ⋯ + n = n(n+1)2. (We met this Gauss formula in 26.2; here we prove it airtight.)
Base case (n = 1). The left side is just 1. The right side is 1·22 = 1. They match, so P(1) holds ✓. The first domino falls.
Inductive step. Assume P(k), i.e. Sk = k(k+1)2, for some k ≥ 1. We must show P(k+1), i.e. Sk+1 = (k+1)(k+2)2. The next partial sum is the old one plus one more term, (k+1):
Sk+1 = Sk + (k+1) = k(k+1)2 + (k+1) = k(k+1) + 2(k+1)2 = (k+1)(k+2)2.
The middle move used the hypothesis — we replaced Sk by k(k+1)/2 — and then factored out the common (k+1): k(k+1) + 2(k+1) = (k+1)(k + 2). That is exactly P(k+1). ✓ Base case and inductive step both done, so the formula holds for every positive integer n.
Dial k and watch the two sides of the step — Sk + (k+1) and (k+1)(k+2)/2 — compute and land equal (green ✓). The partial-sum dots sit exactly on the parabola n(n+1)/2, so the figure can't lie.
Induction is not only for sums. Let P(n) be "5n − 1 is divisible by 4." The trick for divisibility is to peel off a factor and reuse the hypothesis.
Base case (n = 1). 51 − 1 = 4 = 4 · 1, divisible by 4. P(1) holds ✓.
Inductive step. Assume 5k − 1 = 4m for some integer m (this is the hypothesis — 5k − 1 is a multiple of 4). Look at the next case and split off one factor of 5:
5k+1 − 1 = 5 · 5k − 1 = 5(5k − 1) + 5 − 1 = 5 · 4m + 4 = 4(5m + 1).
The result is 4 times the integer (5m + 1), so 5k+1 − 1 is divisible by 4 — that is P(k+1). ✓ Notice the engine again: we rewrote the new expression to contain the old one (5k − 1), substituted the hypothesis 4m, and collected. Both steps done, so 5n − 1 is divisible by 4 for every positive integer n. (Check: 52−1 = 24 = 4·6, 53−1 = 124 = 4·31. ✓)
The recurring move is "make the (k+1)-case reveal the k-case." For 5k+1−1 we wrote 5·5k−1 = 5(5k−1) + 4. The first chunk is divisible by 4 because of the hypothesis; the leftover +4 is divisible by 4 on its own. Sum of two multiples of 4 ⇒ a multiple of 4. The same template proves n3 − n is divisible by 6, or 3n − 1 by 2 — find the factor that lets last year's case reappear.
Induction is sturdy only when both facts are nailed down. Drop one and the proof collapses — and it can collapse without looking wrong. Two traps catch beginners.
Here is a famous fake proof that every group of n horses is all one colour. The base case is fine: P(1) — a group of 1 horse is trivially one colour. The inductive step is where the sleight of hand hides: given any k+1 horses, drop one to get a group of k (same colour by hypothesis), put it back and drop a different one (again all one colour), and the two overlapping groups are claimed to force the whole k+1 to share a colour. So the argument asserts P(k) ⇒ P(k+1)… and we "conclude" all horses match.
The conclusion is absurd, so something is broken — and it is the inductive step, not the base case. The overlap argument needs the two smaller groups to actually share a horse, and that holds for every k ≥ 2 — but it fails at the single value k = 1: the link P(1) ⇒ P(2) is false. Going from 1 horse to 2, the two singleton groups have no horse in common, so nothing forces the two horses to match. One broken link in the chain — even with a true base case and every other link sound — and the wave never reaches domino 2. The implication must hold at every k, with no exceptions.
This is a different failure mode from a missing or false base case. There the inductive step might be flawless at every k, but with no first domino pushed, nothing ever starts — the chain is perfect yet idle. (For instance, "2n > n2" has a sound step for large n but a false base at n = 2, 3, 4, so it is not true for all n.) Both modes break the proof; diagnose which link is missing — the spark, or one of the connections.
The inductive step must use the assumption P(k). If your argument for P(k+1) never refers back to P(k) — if you secretly re-prove the (k+1)-case from scratch, or quietly assume P(k+1) itself — there is no link between the dominoes. Each one would have to be pushed by hand, and the infinity escapes you. A correct step always contains a line where the old case is substituted in (as we did: replace Sk by k(k+1)/2, or 5k−1 by 4m).
No base case = no proof: the dominoes never start — there is nothing to push the first one. A step that fails at even one k = no proof: the chain has a broken link, so the wave stalls there (the "all horses" fallacy — the link P(1) ⇒ P(2) is false). No real use of the hypothesis = no proof: the dominoes don't touch, so the wave can't travel. And do not assume P(k+1) to prove P(k+1) — that is circular. A clean induction reads: base case ✓; assume P(k); from it derive P(k+1) for every k ✓; therefore P(n) for all n.
Mathematical induction proves a statement P(n) for every positive integer with one finite argument, by securing two facts — a base case and a link that carries it forward. Keep this template at hand:
| Step | What you do | Domino picture |
|---|---|---|
| ① Base case | Check P(1) directly (it is true) | the first domino falls |
| ② Inductive step | Assume P(k), then prove P(k+1) — and actually use P(k) | each fallen one topples the next |
| Conclusion | P(n) holds for all positive integers n | they all fall |
| do | check the base case; make the step hold at every k by substituting the hypothesis into the (k+1)-case | chain links |
| don't | skip the base case · let the step fail at one k (e.g. P(1)⇒P(2)) · assume P(k+1) · forget to use P(k) | step breaks ⇒ "all horses same colour" |
The base case is not optional, and the inductive step is worthless unless it genuinely uses the hypothesis. Next, in 26.6, we put sequences to work — saving, compounding, loans, and Fibonacci's rabbits, whose ratio creeps toward the golden ratio φ ≈ 1.618.
Aïsha tests the claim "n2 − n + 41 is prime" for n = 1, 2, 3 and finds 41, 43, 47 — all prime. She declares the claim proved for every n. What is wrong, and at which n does the claim first fail?
Checking a few cases is never a proof for all n — a pattern can break later. This one first fails at n = 41: f(41) = 412 − 41 + 41 = 412 = 1681 = 41 × 41, which is composite. Forty primes in a row proved nothing.
In a proof of P(n) by induction, what are the two required steps, and which one is "the first domino falls"?
① Base case: show P(1) is true — this is "the first domino falls." ② Inductive step: assume P(k) (the inductive hypothesis) and prove P(k+1) — this is "each fallen domino topples the next." Both are required; together they give P(n) for all positive integers n.
Complete the inductive step for 1 + 2 + ⋯ + n = n(n+1)2: assuming Sk = k(k+1)/2, show Sk+1 = (k+1)(k+2)/2.
Sk+1 = Sk + (k+1) = k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)]/2 = (k+1)(k+2)/2 ✓. The hypothesis was used to replace Sk, then (k+1) was factored out. This is exactly P(k+1).
Prove by induction that 5n − 1 is divisible by 4 for every positive integer n.
Base: 51 − 1 = 4 = 4·1 ✓. Step: assume 5k − 1 = 4m for some integer m. Then 5k+1 − 1 = 5·5k − 1 = 5(5k − 1) + 4 = 5·4m + 4 = 4(5m + 1), a multiple of 4 ✓. So the claim holds for all n.
The "all horses are the same colour" argument has a valid-looking inductive step but a false conclusion. The base case P(1) is actually true — so exactly which piece of the proof fails, and why?
The base case is fine (a group of 1 horse is one colour); it is the inductive step that fails — and only at one value. The link P(1) ⇒ P(2) is false: the overlap trick needs the two smaller groups to share a horse, but going from k = 1 to k = 2 there is no shared horse (one horse each, removed in turn). The implication holds for every k ≥ 2 but breaks at k = 1, so the chain has a broken link and the wave never reaches domino 2. A step that fails at even one k proves nothing, even with a true base case.
In an inductive step, a student writes "Assume P(k+1) is true… therefore P(k+1) is true." What rule of induction has been broken, and what should they have assumed instead?
They assumed the very thing to be proved — that is circular. The inductive hypothesis you are allowed to assume is P(k) (the previous case), and from it you must derive P(k+1). Assuming P(k+1) skips the link between the dominoes, so nothing is proved.
Six questions to lock it in. Tap the answer you think is right.
This lesson develops the Standards for Mathematical Practice MP3 (construct viable arguments and critique the reasoning of others): students see that empirical pattern-spotting is a conjecture, not a proof, and learn the two-part deductive template of induction. It builds the algebraic fluency of HSA-SSE.A.2 and HSA-SSE.B.4 (rewriting expressions and reasoning about series), proving the arithmetic-series sum 1 + 2 + ⋯ + n = n(n+1)/2 rather than merely asserting it, and connects to HSF-BF.A.1/A.2 by treating a partial-sum sequence Sn as a function of n. The n2−n+41 trap makes precise why checking cases is not a proof, and the "all horses" counterexample shows that the inductive step must hold at every k — a single broken link (here P(1) ⇒ P(2)), even with a true base case, voids the argument.