Two halves, and both are essential.
Push the first domino but leave a gap in the row, and the falling stops. Space them properly but never push, and nothing falls at all. Induction needs both.
- Home
- Grade 7-12 Math Review
- Mathematical Induction
Mathematical Induction
Show the first domino falls, and that each falling domino knocks over the next.
Choose the missing half
A proof by induction shows the statement holds for n = 1. What must it show next?
The inductive step proves a conditional: assuming the statement at k, it must follow at k + 1. A only ever covers finitely many cases, however many you check. C is what induction exists to avoid — proving infinitely many statements one at a time is impossible.
The base case is usually one line.
claim: 1 + 2 + … + n = n(n + 1)2
state it clearly
n = 1: left side = 1
one term only
right side = 1(2)2 = 1
they match ✓
Short as it is, the base case cannot be skipped. Without it a perfectly valid inductive step proves nothing at all, because there is no first domino to push.
The opposite slip fails too: checking n = 1, 2, 3, 4, 5, 6 by hand proves those six cases and nothing more. Only the inductive step carries the claim past the values we tried.
Assume at k, then build k + 1 out of it.
assume 1 + 2 + … + k = k(k + 1)2
the inductive hypothesis
add (k + 1) to both sides
the one move that matters
= k(k + 1)2 + (k + 1)
use the assumption
= (k + 1)k + 22 ✓
exactly the formula at k + 1
Factor (k + 1) out: (k + 1)[k2 + 1] = (k + 1)k + 22. The target is the original formula with k + 1 written in place of n, so write that target down first and aim at it.
Assuming the case is not the same as assuming the answer.
allowed
assume it holds AT k
the hypothesis
the goal
deduce it holds at k + 1
what you must show
not allowed
assume it holds for ALL n
that is the thing being proved
The hypothesis is one case, not the whole claim
It can feel like cheating to assume what you are proving. It is not: you assume one unnamed case and show the next must follow. That conditional, plus the base case, is what reaches every n.
Variations: a square, a power of 2, and an inequality that starts at 3.
The same two halves each time. Only the algebra in the step changes.
Odd numbers: 1 + 3 + 5 + … + (2n − 1) = n²
n = 1: 1 = 1² ✓
base case
assume 1 + 3 + … + (2k − 1) = k²
the hypothesis
add the next odd number, 2(k + 1) − 1 = 2k + 1
the next term, not just "2k − 1 again"
k² + 2k + 1 = (k + 1)² ✓
a perfect square
The next term is the formula's term with k + 1 in place of n. Writing 2k − 1 again is the usual slip.
Powers of 2: 1 + 2 + 4 + … + 2n − 1 = 2ⁿ − 1
n = 1: 1 = 2¹ − 1 ✓
base case
assume 1 + 2 + … + 2k − 1 = 2ᵏ − 1
the hypothesis
add 2ᵏ: 2ᵏ − 1 + 2ᵏ = 2 · 2ᵏ − 1
two copies of 2ᵏ
= 2k + 1 − 1 ✓
the target
The key fact is 2ᵏ + 2ᵏ = 2k + 1; the exponent goes up by one, it does not double.
An inequality with a later start: 2ⁿ > 2n + 1 for n ≥ 3
n = 3: 8 > 7 ✓
base case at 3, since n = 2 fails (4 > 5 is false)
assume 2ᵏ > 2k + 1 for some k ≥ 3
the hypothesis
2k + 1 = 2 · 2ᵏ > 2(2k + 1) = 4k + 2
double both sides
4k + 2 > 2k + 3 = 2(k + 1) + 1 ✓
because 2k > 1
The base case is the first n the claim is about, not always 1. For an inequality the step ends with a chain of "greater than", not an equals.
Divisibility proofs follow the same shape.
n = 1: 3 − 1 = 2, divisible by 2 ✓
base case
assume 3ᵏ − 1 = 2m
for some whole number m
3k+1 − 1 = 3(3ᵏ) − 1 = 3(2m + 1) − 1
3ᵏ = 2m + 1 from the assumption
= 6m + 2 = 2(3m + 1) ✓
a multiple of 2
Writing the assumption as an equation — 3ᵏ − 1 = 2m — is what makes it usable. "It is divisible by 2" cannot be substituted into anything; "it equals 2m" can.
On the exam
Exams ask for a short proof of a sum formula or a divisibility fact, and multiple-choice tests ask which part is missing or what may be assumed. The fastest route: check the first value, write the hypothesis as an equation, write the k + 1 target down, then add the next term or substitute and aim at the target. A 10-second check: test the formula at n = 2 or 3 by hand before proving it.
Now you try
Practice problem
Spot the flaw
A proof shows that IF a statement holds at n = k then it holds at n = k + 1, but never checks any particular value. What is wrong?
The chain of implications is fine, but it is never triggered. "If n = k then n = k + 1" can be perfectly true for a statement that holds for no n at all — the dominoes are spaced correctly and nobody pushed the first one.
Hint: ask what the inductive step alone actually establishes. It is a conditional, and a conditional with nothing to feed it proves nothing.