Proof by induction — the 3-step method (IB Math AA HL)
Updated October 2026
Quick answer: Show the statement is true for n = 1, assume it is true for n = k, use that assumption to prove it for n = k + 1, then write the conclusion: true for n = 1 and true for k implies true for k + 1, so true for all n ∈ ℤ⁺.
Base case, inductive step, conclusion. HL AA's flagship proof topic — every year at least one 5-mark question. Memorise the layout.
Practise Proof by induction — the 3-step method with AI marking
Open the full HL AA engine — every question in this unit is worked through with instant AI-graded feedback on your handwritten workings.
Basis: show P(1) is true (or the first value the question gives).
Assumption: 'Assume P(k) is true for some k ∈ ℤ⁺' and write out what P(k) says.
Inductive step: start from the k + 1 case and make the assumption appear. Show clearly the line where you use it.
Conclusion: 'Since P(1) is true and P(k) true implies P(k + 1) true, P(n) is true for all n ∈ ℤ⁺ by mathematical induction.' Mark schemes give a mark for this sentence, so write it in full.
For divisibility, split the k + 1 term so the k term appears: 5ᵏ⁺¹ = 5 × 5ᵏ.
Worked example
Prove by induction that 5ⁿ − 1 is divisible by 4 for all n ∈ ℤ⁺.
n = 1: 5¹ − 1 = 4, which is divisible by 4, so P(1) is true.
Assume P(k) is true for some k ∈ ℤ⁺: 5ᵏ − 1 = 4m for some integer m, so 5ᵏ = 4m + 1.
Then 5ᵏ⁺¹ − 1 = 5 × 5ᵏ − 1 = 5(4m + 1) − 1 = 20m + 4 = 4(5m + 1), which is divisible by 4. So P(k + 1) is true.
P(1) is true, and P(k) true implies P(k + 1) true, so P(n) is true for all n ∈ ℤ⁺ by mathematical induction.
Answer: 5ⁿ − 1 = 4 × (an integer) for every positive integer n.
Exam-style HL AA questions on this topic
Proof questions — 38 questions with mark schemes, plus free worked examples
5 quick questions on proof by induction. No sign-in needed.
To prove \(\sum_{r=1}^{n} 3^{r - 1} = \frac{3^n - 1}{2}\) by induction, you assume it is true for \(n = k\). What do you add to both sides to get the case \(n = k + 1\)?
To prove that \(7^n - 1\) is divisible by 6 by induction, you write \(7^{k+1} - 1 = 7(7^k - 1) + m\). Find \(m\).
To prove that \(5^n + 3\) is divisible by 4 by induction, you write \(5^{k+1} + 3 = 5(5^k + 3) + m\). Find \(m\).
To prove \(\sum_{r=1}^{n} (2r - 1) = n^2\) by induction, you assume it is true for \(n = k\). What do you add to both sides to get the case \(n = k + 1\)?
To prove \(\sum_{r=1}^{n} r(r + 1) = \frac{n(n + 1)(n + 2)}{3}\) by induction, you assume it is true for \(n = k\). What do you add to both sides to get the case \(n = k + 1\)?
What do you write at the end of a proof by induction?
A sentence that names both parts: since the statement is true for n = 1, and true for n = k implies true for n = k + 1, it is true for all n ∈ ℤ⁺ by mathematical induction.
Where can I practise proof by induction questions?
On the Proof questions page: 38 exam-style HL AA questions with full mark schemes, plus free step-by-step worked examples.
Can I use my calculator for proof by induction?
In HL AA, Paper 1 is non-calculator and the other papers allow a GDC, so learn the exact method as well as the calculator one.