Proof by Induction | 9231 Further Pure P1

1. The Principle of Mathematical Induction

Mathematical induction proves that a statement Pₙ is true for every positive integer n. It works like a chain of dominoes: if the first falls (base case) and each falling domino knocks over the next (inductive step), then all dominoes must eventually fall.

⭐ The Two-Step Logic

Step 1Show P₁ is true (base case — the first domino falls)

Step 2Assume Pₖ is true, then prove Pₖ₊₁ is true (inductive step)

ConclusionBy (1) and (2), Pₙ is true for all positive integers n

2. Four Proof Types

Type 1 Series / Summation e.g. Prove Σr⁴ = ¼n²(n+1)²
e.g. Prove Σr·r! = (n+1)!−1

Type 2 Sequences / Recurrence e.g. Prove uₙ = 2(1+3ⁿ⁻¹) where uₙ₊₁ = 3uₙ−4, u₁=4
e.g. Prove formula for nth term

Type 3 Matrix Powers e.g. Prove [[a,b],[c,d]]ⁿ = [[...]]
Multiply Mᵏ by M to get Mᵏ⁺¹

Type 4 Divisibility e.g. Prove 3²ⁿ⁺²+5ⁿ⁻³ ≡ 0 (mod 8)
e.g. Prove f(k+1)−f(k) is divisible by d

3. The Standard Skeleton — Words That Earn Marks

Cambridge mark schemes award marks for each stage of the proof. The language must be precise. A correct answer with sloppy language can lose marks.

📋 Standard Proof Template — Use This Every Time

Statement

Let Pₙ be the statement: [write the exact proposition clearly]

e.g. "Let Pₙ be the statement: Σᵣ₌₁ⁿ r² = ⅙n(n+1)(2n+1)"

Base Case

When n = 1: LHS = [compute left side], RHS = [compute right side]. Since LHS = RHS, P₁ is true.

Always verify BOTH sides. Never just compute one side and say "true".

Inductive Hypothesis

Assume Pₖ is true for some positive integer k, i.e. assume [write Pₖ explicitly].

Write "Assume Pₖ is true for some fixed k ∈ ℤ⁺". Never write "assume n = k" — this is incorrect.

Inductive Step

Target: prove Pₖ₊₁ is true, i.e. prove [write Pₖ₊₁ explicitly].

[Working...] Use the inductive hypothesis to rewrite the expression. Manipulate algebraically to reach the Pₖ₊₁ statement.

Start from the LHS of Pₖ₊₁, introduce the IH, and work towards the RHS. Do not start from the answer.

Conclusion

✓ Required Conclusion Statement Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, Pₙ is true for all positive integers n.

Cambridge requires ALL of: "P₁ is true", "Pₖ true implies Pₖ₊₁ true", "by mathematical induction", "for all positive integers n". Missing any part can lose a mark.

4. Language — Right vs Wrong

✓ Correct Language

"Assume Pₖ is true for some fixed k ∈ ℤ⁺"

"Assume [explicit formula for k]"

"We need to show Pₖ₊₁ is true, i.e. [write it]"

"Using the inductive hypothesis..."

"...which is the statement Pₖ₊₁. ✓"

"By the Principle of Mathematical Induction, Pₙ is true for all n ∈ ℤ⁺"

✗ Incorrect / Penalised

"Assume n = k" — wrong, n is the variable

"Let n = k" — same error

Skipping the explicit statement of Pₖ

Not writing Pₖ₊₁ as a target before working

"Therefore true for all n" — incomplete conclusion

Circular argument: using Pₖ₊₁ to prove Pₖ₊₁

5. Divisibility Proofs — The Key Technique

For divisibility by d: express f(k+1) in terms of f(k), then factor out d.

⭐ The Factoring Strategy

Write f(k+1) = [expression involving f(k) or kth-power term]. Substitute the inductive hypothesis f(k) = d·m, then show the result contains d as a factor.

Assume: f(k) is divisible by d, i.e. f(k) = d·m for some integer m

Compute: f(k+1) in terms of f(k) (often multiply by base or use index laws)

Example: f(n) = 5ⁿ(4n+1)−1. Then f(k+1) = 5·f(k) + [correction term]

Factor: f(k+1) = 5·(8m) + 8·[something] = 8(5m + something) shows div. by 8

6. Conjecture from Limited Trial

Sometimes Cambridge asks you to conjecture a formula by computing the first few values, then prove it by induction.

1Compute several values of the expression (n=1,2,3,4) and build a table.
2Spot the pattern — look for polynomial, exponential, or factorial structure.
3Write the conjecture clearly: "I conjecture that [formula]".
4Prove by induction using the standard skeleton above.

💡 Syllabus Examples for Conjecture

Conjecture 1Find the nth derivative of xeˣ — compute d/dx, d²/dx², d³/dx³, spot pattern: dⁿ/dxⁿ(xeˣ) = (x+n)eˣ

Conjecture 2Find Σᵣ₌₁ⁿ r·r! — compute for n=1,2,3: values 1, 4, 18 → pattern: (n+1)!−1

Example 1 Series — Proving a Summation Formula ★★☆ Challenging

Prove by mathematical induction that Σᵣ₌₁ⁿ r(r+1) = ⅓n(n+1)(n+2) for all positive integers n.

1

Define the statement

Let Pₙ be the statement: Σᵣ₌₁ⁿ r(r+1) = ⅓n(n+1)(n+2).

2

Base case n = 1

LHS= 1 × 2 = 2

RHS= ⅓ × 1 × 2 × 3 = 2

Since LHS = RHS = 2, P₁ is true.

3

Inductive hypothesis

Assume Pₖ is true for some fixed k ∈ ℤ⁺, i.e. assume:

Σᵣ₌₁ᵏ r(r+1)= ⅓k(k+1)(k+2)

4

Inductive step — target: prove Pₖ₊₁

We need to show: Σᵣ₌₁ᵏ⁺¹ r(r+1) = ⅓(k+1)(k+2)(k+3).

LHS of Pₖ₊₁= Σᵣ₌₁ᵏ r(r+1) + (k+1)(k+2)

= ⅓k(k+1)(k+2) + (k+1)(k+2) [by inductive hypothesis]

= (k+1)(k+2)[k/3 + 1]

= (k+1)(k+2) × (k+3)/3

= ⅓(k+1)(k+2)(k+3) ✓

This is exactly the RHS of Pₖ₊₁, so Pₖ₊₁ is true.

5

Conclusion

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, Pₙ is true for all positive integers n.

Example 2 Divisibility Proof ★★☆ Challenging

Prove by induction that 3²ⁿ⁺² + 5ⁿ⁻³ is divisible by 8 for all positive integers n.
(Note: we interpret this as f(n) = 9·3²ⁿ + 5ⁿ/125... let us instead prove the cleaner syllabus version: 3²ⁿ⁺² − 5ⁿ⁺³ is divisible by... Actually, let us prove the standard example: 5ⁿ(4n+1) − 1 is divisible by 8.)

Prove by mathematical induction that f(n) = 3²ⁿ − 1 is divisible by 8 for all n ≥ 1.

1

Define and base case

Let Pₙ: f(n) = 3²ⁿ − 1 is divisible by 8.

n=1: f(1)= 3² − 1 = 9 − 1 = 8 = 8 × 1 ✓

P₁ is true.

2

Inductive hypothesis

Assume Pₖ is true for some fixed k ∈ ℤ⁺: 3²ᵏ − 1 = 8m for some integer m.

So 3²ᵏ = 8m + 1.

3

Inductive step

Target: prove 3²⁽ᵏ⁺¹⁾ − 1 is divisible by 8.

f(k+1)= 3²⁽ᵏ⁺¹⁾ − 1 = 3²ᵏ⁺² − 1 = 9 · 3²ᵏ − 1

= 9(8m + 1) − 1 [by inductive hypothesis]

= 72m + 9 − 1

= 72m + 8

= 8(9m + 1)

Since 9m+1 is an integer, f(k+1) is divisible by 8. Pₖ₊₁ is true.

4

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, 3²ⁿ − 1 is divisible by 8 for all positive integers n.

Example 3 Matrix Power Proof ★★★ A* Level

Let M = [[1, 1], [0, 2]]. Prove by induction that Mⁿ = [[1, 2ⁿ−1], [0, 2ⁿ]] for all positive integers n.

1

Base case n = 1

M¹ = M= [[1, 1], [0, 2]]

Formula gives[[1, 2¹−1], [0, 2¹]] = [[1, 1], [0, 2]] ✓

P₁ is true.

2

Inductive hypothesis

Assume Pₖ is true: Mᵏ = [[1, 2ᵏ−1], [0, 2ᵏ]].

3

Inductive step — compute Mᵏ⁺¹ = Mᵏ × M

Target: Mᵏ⁺¹ = [[1, 2ᵏ⁺¹−1], [0, 2ᵏ⁺¹]].

Mᵏ⁺¹= Mᵏ · M = [[1, 2ᵏ−1], [0, 2ᵏ]] · [[1, 1], [0, 2]]

Row 1, Col 1= 1·1 + (2ᵏ−1)·0 = 1

Row 1, Col 2= 1·1 + (2ᵏ−1)·2 = 1 + 2ᵏ⁺¹ − 2 = 2ᵏ⁺¹ − 1 ✓

Row 2, Col 1= 0·1 + 2ᵏ·0 = 0

Row 2, Col 2= 0·1 + 2ᵏ·2 = 2ᵏ⁺¹ ✓

Mᵏ⁺¹= [[1, 2ᵏ⁺¹−1], [0, 2ᵏ⁺¹]] ✓

This is the Pₖ₊₁ formula. Pₖ₊₁ is true.

4

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, Mⁿ = [[1, 2ⁿ−1], [0, 2ⁿ]] for all positive integers n.

Example 4 Conjecture then Prove — Recurrence Relation ★★★ A* Level

A sequence is defined by u₁ = 4 and uₙ₊₁ = 3uₙ − 4. (a) Find u₁, u₂, u₃, u₄ and conjecture a formula for uₙ. (b) Prove your conjecture by induction.

1

Part (a) — Compute terms and conjecture

u₁ = 4

u₂= 3(4) − 4 = 8

u₃= 3(8) − 4 = 20

u₄= 3(20) − 4 = 56

Looking at these: 4, 8, 20, 56... Express as multiples: 4=4×1, 8=4×2, 20=4×5, 56=4×14. The factors are 1, 2, 5, 14 = (3ⁿ⁻¹+1)/2... let us try: uₙ = 2(3ⁿ⁻¹ + 1).

n=1: 2(1+1) = 4✓

n=2: 2(3+1) = 8✓

n=3: 2(9+1) = 20✓

n=4: 2(27+1) = 56✓

Conjecture: uₙ = 2(3ⁿ⁻¹ + 1) for all positive integers n.

2

Part (b) — Prove by induction

Base case n=1: u₁ = 4. Formula gives 2(3⁰+1) = 2(2) = 4. ✓ P₁ true.

Assume Pₖ: uₖ = 2(3ᵏ⁻¹ + 1) for some k ∈ ℤ⁺.

Target Pₖ₊₁: uₖ₊₁ = 2(3ᵏ + 1).

uₖ₊₁= 3uₖ − 4 [by recurrence relation]

= 3 · 2(3ᵏ⁻¹ + 1) − 4 [by inductive hypothesis]

= 6 · 3ᵏ⁻¹ + 6 − 4

= 2 · 3ᵏ + 2

= 2(3ᵏ + 1) ✓

Pₖ₊₁ is true.

3

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, uₙ = 2(3ⁿ⁻¹ + 1) for all positive integers n.

Interactive Proof Explorer

Select a proof type and see a fully worked induction proof with all correct language and stages. Use this to learn the exact structure Cambridge requires.

🔬 Step-by-Step Proof Generator

🧮Induction Verification Tool

Check your base case and first few values. Enter n to verify the formula against the definition.

Proof type

n (up to) 6

Practice Questions

Question 1 — Series

Prove by mathematical induction that Σᵣ₌₁ⁿ r(2r−1) = ⅙n(n+1)(4n−1) for all positive integers n.

Base case n=1: LHS=1(1)=1, RHS=⅙(1)(2)(3)=1 ✓. For inductive step: add the (k+1)th term (k+1)(2(k+1)−1) = (k+1)(2k+1) to both sides. Factor out (k+1) from the resulting expression.

✓ Solution

Base case n=1: LHS = 1(1) = 1. RHS = ⅙(1)(2)(3) = 1. P₁ true ✓

Assume Pₖ: Σᵣ₌₁ᵏ r(2r−1) = ⅙k(k+1)(4k−1).

Target Pₖ₊₁: Σᵣ₌₁ᵏ⁺¹ r(2r−1) = ⅙(k+1)(k+2)(4k+3).

LHS (Pₖ₊₁)= ⅙k(k+1)(4k−1) + (k+1)(2k+1)

= (k+1)[⅙k(4k−1) + (2k+1)]

= (k+1) × [4k²−k+12k+6]/6

= (k+1)(4k²+11k+6)/6

= (k+1)(k+2)(4k+3)/6 = ⅙(k+1)(k+2)(4k+3) ✓

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, Pₙ is true for all positive integers n.

Question 2 — Divisibility

Prove by mathematical induction that n³ + 2n is divisible by 3 for all positive integers n.

For the inductive step, write f(k+1) = (k+1)³+2(k+1). Expand and group: (k³+3k²+3k+1)+(2k+2) = (k³+2k)+(3k²+3k+3). The first bracket is 3m by IH, the second is 3(k²+k+1). So f(k+1) = 3m+3(k²+k+1) = 3(m+k²+k+1).

✓ Solution

Base case n=1: 1+2=3=3×1. P₁ true ✓

Assume Pₖ: k³+2k = 3m for some integer m.

Target: (k+1)³+2(k+1) divisible by 3.

f(k+1)= k³+3k²+3k+1+2k+2 = (k³+2k)+(3k²+3k+3)

= 3m + 3(k²+k+1) = 3(m+k²+k+1) ✓

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, n³+2n is divisible by 3 for all positive integers n.

Question 3 — Matrix Power

Let M = [[3, 2], [0, 1]]. Prove by induction that Mⁿ = [[3ⁿ, 3ⁿ−1], [0, 1]] for all positive integers n.

Base case n=1: M¹=[[3,2],[0,1]], formula gives [[3,3−1],[0,1]]=[[3,2],[0,1]] ✓. For inductive step: compute Mᵏ⁺¹ = Mᵏ × M. You need Row 1, Col 2 = 3ᵏ·2 + (3ᵏ−1)·1 = 2·3ᵏ + 3ᵏ − 1 = 3·3ᵏ − 1 = 3ᵏ⁺¹ − 1 ✓.

✓ Solution

Base case n=1: M¹ = [[3,2],[0,1]]. Formula: [[3¹, 3¹−1],[0,1]] = [[3,2],[0,1]] ✓

Assume Pₖ: Mᵏ = [[3ᵏ, 3ᵏ−1],[0,1]]

Target Pₖ₊₁: Mᵏ⁺¹ = [[3ᵏ⁺¹, 3ᵏ⁺¹−1],[0,1]]

Mᵏ⁺¹ = Mᵏ·M= [[3ᵏ,3ᵏ−1],[0,1]]·[[3,2],[0,1]]

(1,1)= 3ᵏ·3+0 = 3ᵏ⁺¹ ✓

(1,2)= 3ᵏ·2+(3ᵏ−1)·1 = 2·3ᵏ+3ᵏ−1 = 3·3ᵏ−1 = 3ᵏ⁺¹−1 ✓

(2,1) = 0, (2,2)= 0·2+1·1 = 1 ✓

Mᵏ⁺¹= [[3ᵏ⁺¹, 3ᵏ⁺¹−1],[0,1]] ✓

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, Mⁿ = [[3ⁿ, 3ⁿ−1],[0,1]] for all positive integers n.

Question 4 — Conjecture and Prove (A*)

A sequence is defined by u₁ = 1 and uₙ₊₁ = 2uₙ + 1. (a) Find u₁, u₂, u₃, u₄, u₅ and conjecture a closed formula for uₙ. (b) Prove your conjecture by mathematical induction.

(a) Compute: 1, 3, 7, 15, 31. These are 2−1, 4−1, 8−1, 16−1, 32−1 = 2ⁿ−1. Conjecture: uₙ = 2ⁿ−1. (b) Inductive step: use uₖ₊₁ = 2uₖ+1 = 2(2ᵏ−1)+1 = 2ᵏ⁺¹−1.

✓ Solution

(a) u₁=1, u₂=3, u₃=7, u₄=15, u₅=31. Pattern: 2¹−1, 2²−1, 2³−1, 2⁴−1, 2⁵−1.

Conjecture: uₙ = 2ⁿ − 1 for all positive integers n.

(b) Base case n=1: u₁=1. Formula: 2¹−1=1 ✓ P₁ true.

Assume Pₖ: uₖ = 2ᵏ−1.

Target Pₖ₊₁: uₖ₊₁ = 2ᵏ⁺¹−1.

uₖ₊₁= 2uₖ + 1 = 2(2ᵏ−1) + 1 = 2ᵏ⁺¹ − 2 + 1 = 2ᵏ⁺¹ − 1 ✓

✓ Conclusion Since P₁ is true, and Pₖ being true implies Pₖ₊₁ is true, by the Principle of Mathematical Induction, uₙ = 2ⁿ−1 for all positive integers n.

Formula Reference Sheet

Complete reference for Proof by Induction — Cambridge 9231 P1, Section 1.7.

Standard Skeleton

1. State Pₙ clearly

2. Verify P₁ (both sides)

3. Assume Pₖ true (write it)

4. State target Pₖ₊₁

5. Prove Pₖ₊₁ from Pₖ

6. Full conclusion statement

Required Conclusion Words

"P₁ is true"

"Pₖ true implies Pₖ₊₁ true"

"Principle of Mathematical Induction"

"for all positive integers n"

Series Type

Split: Σᵏ⁺¹ = Σᵏ + (k+1)th term

Sub IH, factor out common

Show = Pₖ₊₁ formula

Divisibility Type

Assume f(k) = dm

Express f(k+1) using f(k)

Factor to show = d×integer

Matrix Type

Assume Mᵏ = [formula]

Compute Mᵏ⁺¹ = Mᵏ × M

Show each entry = Pₖ₊₁

Conjecture Type

Compute n=1,2,3,4 values

Identify pattern → conjecture

Then prove by standard induction

📋 Cambridge Exam Strategy — Proof by Induction

Write Pₖ and Pₖ₊₁ explicitly before doing any algebra. Cambridge awards a mark just for correctly stating the inductive hypothesis.
For series: always start LHS(Pₖ₊₁) = Σᵏ term + (k+1)th term, then substitute the IH. Never start from the RHS — that is circular reasoning.
For divisibility: the factoring step is the key mark. Write f(k+1) = [expression with f(k)], sub f(k)=dm, then factor. State explicitly "which is divisible by d since [integer expression] is an integer".
For matrices: compute each entry of Mᵏ⁺¹ separately and label them clearly. Show entry (1,2) carefully — this is where algebra errors typically occur.
The conclusion statement earns a mark — write it in full every time, with all four required elements. A two-word conclusion "QED" will not score.
For conjecture questions: compute at least n=1,2,3,4 and state the conjecture as a clear formula before beginning the proof.

🎉 P1 Complete — All 7 Lessons

You have now completed the full 9231 Further Pure Mathematics Paper 1 course on GPM Education:

✓ Lesson 1.1Roots of Polynomial Equations

✓ Lesson 1.2Rational Functions and Graphs

✓ Lesson 1.3Summation of Series

✓ Lesson 1.4Matrices and Transformations

✓ Lesson 1.5Polar Coordinates

✓ Lesson 1.6Vectors in 3D Space

✓ Lesson 1.7Proof by Mathematical Induction

Proof byMathematical Induction

1. The Principle of Mathematical Induction

2. Four Proof Types

3. The Standard Skeleton — Words That Earn Marks

4. Language — Right vs Wrong

5. Divisibility Proofs — The Key Technique

6. Conjecture from Limited Trial

Interactive Proof Explorer

Practice Questions

Formula Reference Sheet

Proof by
Mathematical Induction