Mathematical Induction (AA HL)
Mathematical induction proves a statement holds for every integer in a range by climbing a ladder: show it's true at the bottom rung, then show that whenever it's true on one rung it must be true on the next. This page walks through the four-part structure examiners expect, with full worked proofs and the slips that cost marks even when the maths itself is right. It's part of the broader Proof topic.
20 questions on this sub-topic.
The proof structure
Covered under IB syllabus reference AHL1.15: proof by mathematical induction, which links to a wide variety of topics including complex numbers (De Moivre's theorem), differentiation, sums of series and divisibility.
The four stages
Base case → hypothesis → inductive step → conclusion
Not in the formula booklet - this is a method to learn, not a formula to look up. Every induction proof follows exactly this shape.
A common target: sum of naturals
\(\displaystyle\sum_{r=1}^n r = \dfrac{n(n+1)}{2}\)
Not in the booklet itself, but derivable from the arithmetic series formula - a frequent statement to prove by induction.
A common target: sum of cubes
\(\displaystyle\sum_{r=1}^n r^3 = \dfrac{n^2(n+1)^2}{4}\)
Also not in the booklet. Divisibility statements (like "\(n^3-n\) is divisible by 6") are just as common as sum statements.
Induction also proves De Moivre's theorem, \((\cos\theta+i\sin\theta)^n=\cos n\theta+i\sin n\theta\), which is in the booklet - see the full Proof page for GDC pointers on checking your algebra.
Worked examples
Prove by mathematical induction that \(\displaystyle\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}\) for all positive integers \(n\).
Worked solution
Base case: \(n=1\): LHS \(= 1\), RHS \(= \dfrac{1 \cdot 2}{2} = 1\). True. A1
Inductive step: Assume true for \(n=k\): \(\displaystyle\sum_{r=1}^{k} r = \dfrac{k(k+1)}{2}\). M1
For \(n = k+1\): \(\displaystyle\sum_{r=1}^{k+1} r = \frac{k(k+1)}{2} + (k+1)\) M1
\(= \dfrac{k(k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}\) A1
This is the formula with \(n = k+1\). A1
Since the base case holds and the inductive step is proven, the result is true for all positive integers \(n\). R1
Prove by mathematical induction that \(n^3 - n\) is divisible by 6 for all positive integers \(n\).
Worked solution
Base case: \(n=1\): \(1-1 = 0 = 6 \times 0\). Divisible by 6. A1
Inductive step: Assume \(k^3 - k = 6m\) for some integer \(m\). M1
\((k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1\) M1
\(= (k^3 - k) + 3k^2 + 3k = 6m + 3k(k+1)\) A1
Since one of \(k, k+1\) is even, \(k(k+1)\) is even, so \(3k(k+1)\) is divisible by 6. R1
Hence \((k+1)^3 - (k+1)\) is divisible by 6. True for all \(n\) by induction. A1 AG
Common mistakes
- Skipping or rushing the base case. Without an explicit, correct verification at the starting value, the whole induction has no foundation to climb from - it's worth a mark on its own.
- Not actually using the assumption for \(n=k\). The inductive step must show the \(n=k+1\) case by substituting the assumed \(n=k\) result into the working - simply re-deriving the target formula from scratch earns no method credit.
- Missing or vague conclusion. "So it's true" is not enough - the final line needs to reference that the base case holds, the inductive step is proven, and hence the statement is true for all \(n\) (in the stated range) by mathematical induction.
Ready to practise properly?
20 induction questions, marked instantly like the real exam.
Quick answers
What are the four stages of a proof by induction?
State and verify the base case, assume the statement holds for \(n=k\) (the inductive hypothesis), show it must then hold for \(n=k+1\), and conclude that it holds for all \(n\) in the stated range by the principle of mathematical induction.
Why can't you skip the base case in an induction proof?
The inductive step only shows that truth passes from \(n=k\) to \(n=k+1\) - it never shows the statement is true anywhere on its own. Without a verified starting point there's nothing for that chain of implications to start from, so the whole proof has no foundation.