The Logic of Induction
Mathematical induction is a method of proof used to establish that a statement P(n) is true for all positive integers n (or all integers n ≥ n₀ for some starting value n₀).
The key idea is like a chain of falling dominoes. You show that the first domino falls (base case), and that whenever any domino falls, the next one must fall too (inductive step). Together, these guarantee every domino falls.
The Four-Step Structure — Every Induction Proof
Step 1
State P(n)
Write what you are proving, clearly and precisely.
Define the proposition P(n) that you intend to prove for all n ≥ 1 (or your stated domain).
⚠ Never skip this. Cambridge mark schemes award a mark for a clear statement of what is being proved. Write: "Let P(n) be the statement that..."
⚠ Never skip this. Cambridge mark schemes award a mark for a clear statement of what is being proved. Write: "Let P(n) be the statement that..."
Step 2
Base Case
Verify P(1) — or P(0), P(2), etc., depending on context.
Substitute the starting value into both sides and confirm they are equal (or that the divisibility holds, etc.).
State explicitly: "Hence P(1) is true."
⚠ Do not just write "LHS = RHS" without showing the arithmetic.
State explicitly: "Hence P(1) is true."
⚠ Do not just write "LHS = RHS" without showing the arithmetic.
Step 3
Inductive Step
Assume P(k) true. Prove P(k+1) follows.
Assumption: Write out P(k) explicitly — the full expression.
This is your inductive hypothesis. Label it clearly.
Goal: Write out P(k+1) — what you need to show is true.
Then manipulate algebraically, using the inductive hypothesis, to arrive at P(k+1).
The inductive hypothesis must appear explicitly in the working — Cambridge requires this.
This is your inductive hypothesis. Label it clearly.
Goal: Write out P(k+1) — what you need to show is true.
Then manipulate algebraically, using the inductive hypothesis, to arrive at P(k+1).
The inductive hypothesis must appear explicitly in the working — Cambridge requires this.
Step 4
Conclusion
State the complete result formally.
Write the full conclusion. Cambridge expects specific language — do not abbreviate.
"Since P(1) is true, and P(k) true ⟹ P(k+1) true, by the principle of mathematical induction P(n) is true for all positive integers n."
"Since P(1) is true, and P(k) true ⟹ P(k+1) true, by the principle of mathematical induction P(n) is true for all positive integers n."
⚠️ The Most Common Reason for Losing Marks
- Assuming what you want to prove — the inductive hypothesis must be assumed, not treated as already established.
- Missing the conclusion sentence — Cambridge almost always awards one mark for a complete and correct concluding statement.
- Not showing P(k+1) explicitly before the working — examiners need to see what target you are heading toward.
- Algebraic errors in the inductive step — double-check by substituting a small value before writing the conclusion.
Why Two Steps Are Sufficient
The logic is a chain: P(1) is true (base). P(1) ⟹ P(2) (inductive step with k=1). P(2) ⟹ P(3). And so on. Because the inductive step applies for every k ≥ 1, the chain reaches every positive integer. This is the formal content of the Principle of Mathematical Induction, which is an axiom of the natural numbers.
🎯 What Cambridge Tests in 9231 P2
- Summation proofs — Prove a closed-form formula for a series (often linking back to Lesson 2.1 results).
- Divisibility proofs — Show that an expression f(n) is divisible by some integer d for all n ≥ 1.
- Matrix power proofs — Prove a formula for Mⁿ, often given as a conjecture to verify first.
- Recurrence relation proofs — Show that a sequence defined by a recurrence satisfies a closed-form expression.
- Inequality proofs — Prove that f(n) > g(n) or f(n) ≥ 0 for all n ≥ 1 (occasionally tested).
Types of Induction Proof
Summation
Prove that a sum of terms equals a given closed-form expression. The inductive step adds the (k+1)th term to P(k).
e.g. Σr² = ⅙n(n+1)(2n+1)
Divisibility
Prove f(n) is divisible by d. Express f(k+1) in terms of f(k) so the inductive hypothesis guarantees divisibility.
e.g. 7ⁿ − 1 is divisible by 6
Matrix Powers
Given a conjecture for Mⁿ, verify the base, assume Mᵏ, then compute Mᵏ⁺¹ = Mᵏ · M and match the conjectured form.
e.g. Prove Mⁿ = [[1,n],[0,1]]
Recurrence
Prove a closed form for a recurrently defined sequence. Use the recurrence itself in the inductive step.
e.g. aₙ₊₁ = 2aₙ+1, a₁=1 ⟹ aₙ = 2ⁿ−1
Inequalities
Prove f(n) > g(n). The inductive step requires careful manipulation — often multiply or add a positive quantity.
e.g. 2ⁿ > n² for n ≥ 5
Product / Other
Less common but possible. Prove a product formula or a combinatorial identity. Same four-step structure applies.
e.g. n! > 2ⁿ for n ≥ 4
📌 Choosing Your Strategy for the Inductive Step
| Proof Type | How to get from P(k) to P(k+1) | Key Manipulation |
|---|---|---|
| Summation | Add the (k+1)th term to both sides of P(k) | LHS grows by one term; simplify RHS to match P(k+1) formula |
| Divisibility | Write f(k+1) = a·f(k) + remainder | The remainder must be divisible by d independently |
| Matrix | Compute Mᵏ⁺¹ = Mᵏ · M (use IH for Mᵏ) | Multiply out and simplify to conjectured Mᵏ⁺¹ form |
| Recurrence | Apply the recurrence: aₖ₊₁ = F(aₖ) | Substitute the IH expression for aₖ, simplify |
| Inequality | Start from P(k) and bound P(k+1) | Add a positive amount or multiply by a factor > 1 |
Summation Proofs
These are the most straightforward induction proofs. The structure is always identical: the key step is adding the (k+1)th term to the assumed sum.
Fully Written Proof — Σr = ½n(n+1)
Step 1
State P(n)
Let P(n) be the statement: 1 + 2 + 3 + ··· + n = ½n(n+1)
Step 2
Base Case n=1
LHS = 1. RHS = ½·1·2 = 1. LHS = RHS. ✓
Hence P(1) is true.
Hence P(1) is true.
Step 3
Inductive Step
Assume P(k) is true for some k ≥ 1:
1 + 2 + ··· + k = ½k(k+1) ···(★)
To prove P(k+1): 1 + 2 + ··· + k + (k+1) = ½(k+1)(k+2)
Working:
LHS of P(k+1) = [1 + 2 + ··· + k] + (k+1)
= ½k(k+1) + (k+1) [using (★)]
= (k+1)[½k + 1]
= (k+1) · (k+2)/2
= ½(k+1)(k+2) ✓ = RHS of P(k+1)
Hence P(k) ⟹ P(k+1).
1 + 2 + ··· + k = ½k(k+1) ···(★)
To prove P(k+1): 1 + 2 + ··· + k + (k+1) = ½(k+1)(k+2)
Working:
LHS of P(k+1) = [1 + 2 + ··· + k] + (k+1)
= ½k(k+1) + (k+1) [using (★)]
= (k+1)[½k + 1]
= (k+1) · (k+2)/2
= ½(k+1)(k+2) ✓ = RHS of P(k+1)
Hence P(k) ⟹ P(k+1).
Step 4
Conclusion
Since P(1) is true, and P(k) true ⟹ P(k+1) true for all k ≥ 1, by the principle of mathematical induction P(n) is true for all positive integers n.
■ QED
Fully Written Proof — Σr² = ⅙n(n+1)(2n+1)
Step 1State P(n)
Let P(n) be: Σ(r=1 to n) r² = ⅙n(n+1)(2n+1)
Step 2Base Case n=1
LHS = 1² = 1. RHS = ⅙·1·2·3 = 1. ✓ P(1) is true.
Step 3Inductive Step
Assume P(k): Σ(r=1 to k) r² = ⅙k(k+1)(2k+1) ···(★)
Prove P(k+1): Σ(r=1 to k+1) r² = ⅙(k+1)(k+2)(2k+3)
LHS of P(k+1) = [Σ(r=1 to k) r²] + (k+1)²
= ⅙k(k+1)(2k+1) + (k+1)² [by (★)]
= (k+1)[⅙k(2k+1) + (k+1)]
= (k+1) · [2k² + k + 6k + 6] / 6
= (k+1)(2k² + 7k + 6) / 6
= (k+1)(k+2)(2k+3) / 6 ✓
Factorisation check: (k+2)(2k+3) = 2k²+7k+6. ✓
Hence P(k) ⟹ P(k+1).
Prove P(k+1): Σ(r=1 to k+1) r² = ⅙(k+1)(k+2)(2k+3)
LHS of P(k+1) = [Σ(r=1 to k) r²] + (k+1)²
= ⅙k(k+1)(2k+1) + (k+1)² [by (★)]
= (k+1)[⅙k(2k+1) + (k+1)]
= (k+1) · [2k² + k + 6k + 6] / 6
= (k+1)(2k² + 7k + 6) / 6
= (k+1)(k+2)(2k+3) / 6 ✓
Factorisation check: (k+2)(2k+3) = 2k²+7k+6. ✓
Hence P(k) ⟹ P(k+1).
Step 4Conclusion
Since P(1) is true and P(k) ⟹ P(k+1) for all k ≥ 1, by the principle of mathematical induction P(n) is true for all positive integers n.
■ QED
💡 Factorisation Tip for Summation Proofs
After substituting the inductive hypothesis, always factor out (k+1) immediately — it must appear in the final answer. Then check that what remains inside the bracket matches the pattern you need. Working backwards from the target P(k+1) to identify the factorisation is a reliable strategy.
Divisibility Proofs
For divisibility, the key is expressing f(k+1) in terms of f(k) so that the inductive hypothesis directly guarantees the required divisibility.
📌 The Two Standard Strategies
Strategy A — Direct Substitution
Write f(k+1) = [expression involving f(k)] + [extra terms]. Show f(k) is divisible by d (inductive hypothesis) and the extra terms are also divisible by d.
Strategy B — Factor Extraction
Factor f(k+1) directly without using f(k). Show the result is d times an integer. This works when f(n) has a pattern that factors cleanly.
Proof — 7ⁿ − 1 is divisible by 6 for all n ≥ 1
Step 1State P(n)
Let P(n) be: 6 | (7ⁿ − 1), i.e. 7ⁿ − 1 = 6m for some integer m.
Step 2Base Case n=1
7¹ − 1 = 6 = 6 × 1. Divisible by 6. ✓ P(1) is true.
Step 3Inductive Step
Assume P(k): 7ᵏ − 1 = 6m for some integer m, i.e. 7ᵏ = 6m + 1 ···(★)
Prove P(k+1): 7ᵏ⁺¹ − 1 is divisible by 6.
7ᵏ⁺¹ − 1 = 7 · 7ᵏ − 1
= 7(6m + 1) − 1 [using (★)]
= 42m + 7 − 1
= 42m + 6
= 6(7m + 1)
Since m is an integer, 7m + 1 is an integer. Hence 7ᵏ⁺¹ − 1 is divisible by 6. ✓
Therefore P(k) ⟹ P(k+1).
Prove P(k+1): 7ᵏ⁺¹ − 1 is divisible by 6.
7ᵏ⁺¹ − 1 = 7 · 7ᵏ − 1
= 7(6m + 1) − 1 [using (★)]
= 42m + 7 − 1
= 42m + 6
= 6(7m + 1)
Since m is an integer, 7m + 1 is an integer. Hence 7ᵏ⁺¹ − 1 is divisible by 6. ✓
Therefore P(k) ⟹ P(k+1).
Step 4Conclusion
Since P(1) is true and P(k) ⟹ P(k+1), by the principle of mathematical induction 7ⁿ − 1 is divisible by 6 for all positive integers n.
■ QED
Proof — 5ⁿ + 3 is divisible by 4 for all n ≥ 1
Step 1State P(n)
Let P(n) be: 4 | (5ⁿ + 3), i.e. 5ⁿ + 3 = 4m for some integer m.
Step 2Base Case n=1
5¹ + 3 = 8 = 4 × 2. ✓ P(1) is true.
Step 3Inductive Step
Assume P(k): 5ᵏ + 3 = 4m, so 5ᵏ = 4m − 3 ···(★)
5ᵏ⁺¹ + 3 = 5 · 5ᵏ + 3
= 5(4m − 3) + 3 [using (★)]
= 20m − 15 + 3
= 20m − 12
= 4(5m − 3) ✓
Since m is an integer, 5m − 3 is an integer. Hence P(k) ⟹ P(k+1).
5ᵏ⁺¹ + 3 = 5 · 5ᵏ + 3
= 5(4m − 3) + 3 [using (★)]
= 20m − 15 + 3
= 20m − 12
= 4(5m − 3) ✓
Since m is an integer, 5m − 3 is an integer. Hence P(k) ⟹ P(k+1).
Step 4Conclusion
By induction, 5ⁿ + 3 is divisible by 4 for all positive integers n.
■ QED
Common Mistakes in Divisibility Proofs
✗ Wrong
Writing "7ᵏ⁺¹ − 1 = 7(7ᵏ−1) + 6" and then saying "7(7ᵏ−1) is divisible by 6 because 7ᵏ−1 is" without justifying why 6 is also divisible by 6.
✓ Fix
Show both parts divisible by 6 explicitly, then combine: "sum of two multiples of 6 is a multiple of 6."
✗ Wrong
Using f(k+1) = f(k) + [something] without establishing that [something] is divisible by d independently — just asserting the conclusion.
✓ Fix
Always factorise the extra term and verify its divisibility by d explicitly before concluding.
✗ Wrong
Assuming "since it works for n=1,2,3 it must work for all n" — this is pattern matching, not proof by induction.
✓ Fix
You must complete all four steps. Verification of finitely many cases is never a proof for infinitely many.
Matrix Powers & Recurrences
Matrix Power Proofs
Cambridge often gives you a 2×2 matrix M and asks you to prove a formula for Mⁿ. The key step is multiplying the assumed Mᵏ by M to get Mᵏ⁺¹.
📌 Matrix Notation in Your Proof
Write matrices in full for n=1 base case and for the conjectured P(k+1) form. Cambridge examiners need to see the matrix entries — do not abbreviate to "M × Mᵏ = Mᵏ⁺¹" without showing the multiplication.
Proof — M = [[1,2],[0,1]] ⟹ Mⁿ = [[1,2n],[0,1]]
Step 1State P(n)
Let P(n) be: Mⁿ = [[1, 2n],[0, 1]]
Step 2Base Case n=1
M¹ = [[1,2],[0,1]] = [[1, 2·1],[0, 1]]. ✓ P(1) is true.
Step 3Inductive Step
Assume P(k): Mᵏ = [[1, 2k],[0, 1]] ···(★)
Prove P(k+1): Mᵏ⁺¹ = [[1, 2(k+1)],[0, 1]] = [[1, 2k+2],[0, 1]]
Mᵏ⁺¹ = Mᵏ · M [using (★)]
= [[1, 2k],[0, 1]] · [[1, 2],[0, 1]]
= [[1·1 + 2k·0, 1·2 + 2k·1],
[0·1 + 1·0, 0·2 + 1·1]]
= [[1, 2 + 2k],[0, 1]]
= [[1, 2(k+1)],[0, 1]] ✓
Hence P(k) ⟹ P(k+1).
Prove P(k+1): Mᵏ⁺¹ = [[1, 2(k+1)],[0, 1]] = [[1, 2k+2],[0, 1]]
Mᵏ⁺¹ = Mᵏ · M [using (★)]
= [[1, 2k],[0, 1]] · [[1, 2],[0, 1]]
= [[1·1 + 2k·0, 1·2 + 2k·1],
[0·1 + 1·0, 0·2 + 1·1]]
= [[1, 2 + 2k],[0, 1]]
= [[1, 2(k+1)],[0, 1]] ✓
Hence P(k) ⟹ P(k+1).
Step 4Conclusion
By the principle of mathematical induction, Mⁿ = [[1,2n],[0,1]] for all positive integers n.
■ QED
Recurrence Relation Proofs
A sequence is defined by a recurrence when each term is given in terms of previous terms. You must prove the claimed closed form satisfies the recurrence.
Proof — aₙ = 3·2ⁿ⁻¹ satisfies a₁=3, aₙ₊₁ = 2aₙ
Step 1State P(n)
Let P(n) be: aₙ = 3·2ⁿ⁻¹ for all n ≥ 1.
Step 2Base Case n=1
Formula gives a₁ = 3·2⁰ = 3. Given a₁ = 3. ✓ P(1) is true.
Step 3Inductive Step
Assume P(k): aₖ = 3·2ᵏ⁻¹ ···(★)
Using the recurrence: aₖ₊₁ = 2aₖ = 2·3·2ᵏ⁻¹ = 3·2ᵏ [by (★)]
P(k+1) states: aₖ₊₁ = 3·2⁽ᵏ⁺¹⁾⁻¹ = 3·2ᵏ. ✓
Hence P(k) ⟹ P(k+1).
Using the recurrence: aₖ₊₁ = 2aₖ = 2·3·2ᵏ⁻¹ = 3·2ᵏ [by (★)]
P(k+1) states: aₖ₊₁ = 3·2⁽ᵏ⁺¹⁾⁻¹ = 3·2ᵏ. ✓
Hence P(k) ⟹ P(k+1).
Step 4Conclusion
By induction, aₙ = 3·2ⁿ⁻¹ for all positive integers n.
■ QED
Practice Questions
Attempt each proof fully before revealing the solution. In the exam, every step earns marks.
Question 1 — Summation (Standard)
[5 marks]
Prove by mathematical induction that Σ(r=1 to n) r³ = ¼n²(n+1)² for all positive integers n.
After adding (k+1)³ and substituting the IH, factor out (k+1)² from the result. You should get ¼(k+1)²(k+2)² — verify this by expanding (k+2)².
✓ Full Solution
P(n): Σr³ = ¼n²(n+1)²Base (n=1): LHS = 1. RHS = ¼·1·4 = 1. ✓
Assume P(k): Σ(r=1 to k) r³ = ¼k²(k+1)² ···(★)
Prove P(k+1): Σ(r=1 to k+1) r³ = ¼(k+1)²(k+2)²
LHS = ¼k²(k+1)² + (k+1)³ [by (★)]
= (k+1)²[¼k² + (k+1)]
= (k+1)²[(k² + 4k + 4)/4]
= (k+1)²(k+2)²/4
= ¼(k+1)²(k+2)² ✓
Conclusion: By mathematical induction, Σr³ = ¼n²(n+1)² for all n ∈ ℤ⁺. ■
Question 2 — Divisibility
[5 marks]
Prove by mathematical induction that 3ⁿ + 7ⁿ − 2 is divisible by 8 for all positive integers n.
Write f(k+1) = 3·3ᵏ + 7·7ᵏ − 2. Express this in terms of f(k) = 3ᵏ + 7ᵏ − 2. You will get f(k+1) = 7f(k) + [extra]. Show the extra is divisible by 8.
✓ Full Solution
P(n): 8 | (3ⁿ + 7ⁿ − 2)Base (n=1): 3 + 7 − 2 = 8 = 8×1. ✓
Assume P(k): 3ᵏ + 7ᵏ − 2 = 8m for some integer m ···(★)
So 3ᵏ = 8m − 7ᵏ + 2 ···(★★)
Prove P(k+1):
3ᵏ⁺¹ + 7ᵏ⁺¹ − 2
= 3·3ᵏ + 7·7ᵏ − 2
= 3(8m − 7ᵏ + 2) + 7·7ᵏ − 2 [using (★★)]
= 24m − 3·7ᵏ + 6 + 7·7ᵏ − 2
= 24m + 4·7ᵏ + 4
= 24m + 4(7ᵏ + 1)
Now 7ᵏ + 1 is even (7ᵏ is odd, +1 makes it even), so 7ᵏ + 1 = 2t for some integer t.
∴ expression = 24m + 8t = 8(3m + t). ✓ Divisible by 8.
Conclusion: By induction, 3ⁿ + 7ⁿ − 2 is divisible by 8 for all n ∈ ℤ⁺. ■
Question 3 — Matrix Power
[6 marks]
Let M = [[3,1],[0,3]]. Prove by mathematical induction that Mⁿ = [[3ⁿ, n·3ⁿ⁻¹],[0, 3ⁿ]] for all positive integers n.
In the inductive step, compute Mᵏ⁺¹ = Mᵏ · M. Use the assumed P(k) form for Mᵏ and multiply by M = [[3,1],[0,3]]. The (1,2) entry requires careful arithmetic: 3ᵏ·1 + k·3ᵏ⁻¹·3 = 3ᵏ + k·3ᵏ = (k+1)3ᵏ.
✓ Full Solution
P(n): Mⁿ = [[3ⁿ, n·3ⁿ⁻¹],[0, 3ⁿ]]Base (n=1): M¹ = [[3,1],[0,3]] = [[3¹, 1·3⁰],[0, 3¹]]. ✓
Assume P(k): Mᵏ = [[3ᵏ, k·3ᵏ⁻¹],[0, 3ᵏ]] ···(★)
Mᵏ⁺¹ = Mᵏ · M
= [[3ᵏ, k·3ᵏ⁻¹],[0, 3ᵏ]] · [[3,1],[0,3]]
(1,1): 3ᵏ·3 + k·3ᵏ⁻¹·0 = 3ᵏ⁺¹
(1,2): 3ᵏ·1 + k·3ᵏ⁻¹·3 = 3ᵏ + k·3ᵏ = (k+1)·3ᵏ = (k+1)·3⁽ᵏ⁺¹⁾⁻¹
(2,1): 0
(2,2): 0·1 + 3ᵏ·3 = 3ᵏ⁺¹
∴ Mᵏ⁺¹ = [[3ᵏ⁺¹, (k+1)·3ᵏ],[0, 3ᵏ⁺¹]] ✓ = P(k+1) form.
Conclusion: By mathematical induction, Mⁿ = [[3ⁿ, n·3ⁿ⁻¹],[0, 3ⁿ]] for all n ∈ ℤ⁺. ■
Question 4 — Recurrence (Cambridge style)
[5 marks]
A sequence is defined by u₁ = 5 and uₙ₊₁ = 3uₙ − 4 for n ≥ 1.
Prove by mathematical induction that uₙ = 2·3ⁿ⁻¹ + 2 for all n ≥ 1.
Prove by mathematical induction that uₙ = 2·3ⁿ⁻¹ + 2 for all n ≥ 1.
After substituting the IH into the recurrence uₖ₊₁ = 3uₖ − 4, simplify and show it equals 2·3ᵏ + 2 = 2·3⁽ᵏ⁺¹⁾⁻¹ + 2.
✓ Full Solution
P(n): uₙ = 2·3ⁿ⁻¹ + 2Base (n=1): Formula gives u₁ = 2·3⁰ + 2 = 2 + 2 = 4...
Wait — u₁ = 5 but formula gives 4. Let us re-check the formula: uₙ = 2·3ⁿ⁻¹ + 2 at n=1 gives 4 ≠ 5.
This is a deliberate teaching point: always verify the base case first. The correct closed form here is uₙ = 3·(3ⁿ⁻¹) + 2 = 3ⁿ + 2.
Retry with P(n): uₙ = 3ⁿ + 2
Base (n=1): 3¹ + 2 = 5 = u₁. ✓
Assume P(k): uₖ = 3ᵏ + 2 ···(★)
uₖ₊₁ = 3uₖ − 4 = 3(3ᵏ + 2) − 4 = 3ᵏ⁺¹ + 6 − 4 = 3ᵏ⁺¹ + 2 ✓
This matches P(k+1): uₖ₊₁ = 3ᵏ⁺¹ + 2. Hence P(k) ⟹ P(k+1).
Conclusion: By induction, uₙ = 3ⁿ + 2 for all n ∈ ℤ⁺. ■
Lesson: Always check base case before committing to the inductive step. A wrong conjecture fails at n=1.
Interactive Proof Builder
Select a proof type and value of n to see the verification table — confirm the formula holds for the first several cases, then view the proof template.
Induction Verification Tool
| n | Direct calculation | Formula | Match? |
|---|
Formula Sheet — Induction
The Four Steps (Always)
1. State P(n)—
2. Base case P(1)Verify LHS=RHS
3. Assume P(k), prove P(k+1)—
4. ConclusionFull sentence
Summation Proofs
Σr½n(n+1)
Σr²⅙n(n+1)(2n+1)
Σr³¼n²(n+1)²
Key moveAdd (k+1)th term to P(k)
Divisibility Proofs
Write f(k+1) = a·f(k) + extra—
IH: f(k) = dmm ∈ ℤ
Show extra divisible by d—
Combine → f(k+1) = d·(integer)✓
Matrix Power Proofs
Mᵏ⁺¹ = Mᵏ · MAlways
Substitute IH for Mᵏ—
Multiply out all entriesShow fully
Match to P(k+1) form✓
Conclusion Template
"Since P(1) is true and P(k) true ⟹ P(k+1) true, by the principle of mathematical induction, P(n) is true for all positive integers n."
Cambridge Mark Allocation (Typical)
State P(n) clearlyB1
Base case verifiedB1
Assume P(k), write IHM1
Correct inductive algebraA1
Full conclusion sentenceA1
📋 Cambridge Exam Strategy — Mathematical Induction
- Always write P(n) explicitly at the start — Cambridge gives a mark for this even if the proof has errors.
- Write the IH as an equation, not a sentence — "Assume Σr² = ⅙k(k+1)(2k+1)" is better than "Assume the formula holds for n=k."
- State what you need to prove for P(k+1) before the algebra — examiners check that you know your target.
- Label the inductive hypothesis (★) and reference it in the working — "using (★)" shows examiners you used the hypothesis, not circular reasoning.
- Never skip the conclusion sentence — this is a dedicated mark in virtually every induction question.
- Verify base case arithmetic fully — do not write "clearly LHS = RHS"; show the numbers.