Mathematical induction proves infinitely many statements, one for each natural number n, all at once, the way a row of dominoes falls.
First you show that the first domino falls, that is, the statement is true for n = 1; then you show that whenever any domino falls, the next one falls too, that is, if it is true for n = k it is true for n = k + 1.
With both in place, the chain runs on through 1, 2, 3, … without end, and the statement holds for every natural number.
In the first picture, raising the number of fallen dominoes adds to the dominoes leaning on the next one; the second lays out the three steps of the proof in order.
Induction as dominoes
seegongsik.com
Fallen dominoes (gold) lean on the next one as they topple in turn; the red arrow on the left pushes the first
3
💡 Two conditions for every domino to fall
①The first domino is pushed over: the statement is checked for n = 1
②Whichever one falls, the next falls too: true for n = k means true for n = k + 1
③Without either condition, nothing says the whole row falls
④Some problems start from a number other than 1, such as n = 2, and then that number is checked first
How the proof is built: three steps
seegongsik.com
The flow of a proof by induction
📐 What each step does
①Step 1 (base case): put in n = 1 and show the statement holds
②Step 2 (assumption): assume it holds for n = k
③Step 3 (inductive step): use that assumption to show it holds for n = k + 1
④Once all three are done, the proof covers every natural number n
Example: proving 1 + 2 + … + n = n(n + 1)/2
Step 1: n = 1
LHS = 1, RHS = 1×22 = 1
Check directly that both sides are equal for n = 1
Step 2: assume n = k
1+2+...+k = k(k+1)2 (hypothesis)
Assume the formula holds for n = k
Step 3: prove n = k + 1
1+2+...+k+(k+1) = k(k+1)2 + (k+1) = (k+1)(k+2)2
Adding k + 1 to both sides of the assumed formula and simplifying gives the formula for n = k + 1
✅ Proof complete
①The formula holds for n = 1
②If it holds for n = k, it holds for n = k + 1
③So 1 + 2 + … + n = n(n + 1)/2 for every natural number n
Using induction
⚠️ Common Mistakes
①Leave out step 1 and the second condition on its own proves nothing
②Step 2 assumes the statement for n = k; assuming the n = k + 1 statement you are trying to prove is not allowed
③If step 3 never uses the assumption, the proof is not a proof by induction
📐 Where induction is used
①Equalities and inequalities about a natural number n
②Sum formulas for sequences
③Statements about divisibility (for example, 3ⁿ − 1 is a multiple of 2)
④Properties of figures (for example, the interior angles of an n-gon add up to (n − 2) × 180°)
Summary
Mathematical Induction
P(1) ∧ [P(k) → P(k+1)] ⟹ ∀n∈ℕ, P(n)
When the base case and the inductive step both hold, the statement holds for every natural number
🎯 Exam Points
①Three steps: base (n = 1) → assumption (n = k) → proof (n = k + 1)
②Never skip the base case
③The inductive step must use the assumption
④For an inequality, rewrite the left side for n = k + 1 into a form where the assumption fits
⑤Some problems start from a number other than 1, such as n = 2
Worked Examples & Past Exam
Example 1
When proving 1 + 2 + ... + n = n(n+1)/2 for all natural numbers n by mathematical induction, which step must be checked first?
1
Induction has two parts: (i) it holds for n = 1, and (ii) if it holds for n = k, it holds for n = k + 1.
(i) check n = 1, (ii) P(k) ⟹ P(k+1)
2
The very first thing is to put in n = 1 and check that both sides agree.
n=1: left = 1, right = 1×22 = 1
▸ First check that it holds for n = 1 (the base case).
Without checking the starting point, the first domino never falls, however strong the chain "the next one falls too" may be.
Example 2
In induction, after assuming the statement holds at n=k, what must you show using that assumption?
1
Assume it holds for n = k (the induction hypothesis).
assume: P(k) holds
2
Using that assumption as a stepping stone, show that it holds for n = k + 1.
to show: P(k+1) holds
▸ Show that it also holds for n = k + 1.
The heart of the inductive step is finding the n = k expression inside the n = k + 1 one and replacing it using the assumption.
2023 CSAT Math type, adapted
Which two steps of mathematical induction correspond to all the dominoes falling?
①n=1 holds, and P(k) ⟹ P(k+1)
②only n=1 holds
③only P(k) ⟹ P(k+1)
④substitute every n directly
⑤n=2 holds, and P(k) ⟹ P(k−1)
▸ ① n=1 holds, and P(k) ⟹ P(k+1)
1
The first domino falling matches the base case: it holds for n = 1.
(i) holds at n = 1
2
The kth domino falling makes the (k + 1)th fall, which matches the inductive step P(k) ⟹ P(k + 1).