Proof by induction

CIE A-Level Further Mathematics· Further Pure 1 Section 1.1: Proof by mathematical induction for positive integers· 25 min read

1. Core Formal Structure of Induction★★☆☆☆⏱ 5 min

📘 Definition

Principle of Mathematical Induction

If a statement P(n) is true for n=1, and the truth of P(k) implies the truth of P(k+1) for all positive integers k, then P(n) is true for all n ∈ ℕ

📐 Worked Example

Prove that the sum of the first n positive integers equals n(n+1)/2 using induction

1
Step 1: Base Case. Test n=1: LHS = 1, RHS = 1(2)/2 = 1. P(1) is true.
2
Step 2: Inductive Hypothesis. Assume P(k) is true: $\sum_{r = 1}^{k} r = \frac{k ( k + 1 )}{2}$
3
Step 3: Inductive Step. Add (k+1) to both sides: $\sum_{r = 1}^{k + 1} r = \frac{k ( k + 1 )}{2} + (k + 1) = \frac{( k + 1 ) ( k + 2 )}{2}$ , which matches P(k+1)
4
Step 4: Conclusion. Since P(1) is true, and P(k) true implies P(k+1) true, P(n) holds for all positive integers n.

✓ Quick check

Test your understanding of mark weight for induction steps

Which step of a standard induction proof is worth the largest share of marks in a typical 9231 question?
- Base case
- Inductive hypothesis
- Inductive step
- Final conclusion
Reveal answer
Inductive step —
The algebraic manipulation in the inductive step is usually worth 4-6 of the total 8-10 marks for a full induction question.

2. Induction for Summation Identities★★★☆☆⏱ 7 min

Summation proofs are the most frequently asked induction type in CIE 9231 Paper 1. The key rule is to isolate the (k+1)th term from the sum when moving from P(k) to P(k+1), then rearrange to match the required closed form.

\sum_{r=1}^{k+1} f(r) = \sum_{r=1}^{k} f(r) + f(k+1)

📐 Worked Example

Prove that $\sum_{r = 1}^{n} r^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ for all positive integers n

1
Base case n=1: LHS = 1, RHS = 123/6 = 1, so P(1) holds.
2
Inductive hypothesis: Assume $\sum_{r = 1}^{k} r^{2} = \frac{k ( k + 1 ) ( 2 k + 1 )}{2}$
3
Inductive step: Add $(k + 1)^{2}$ to both sides:
4
$\sum_{r=1}^{k+1} r^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$
5
$= \frac{(k+1)}{6} \left[ 2k^2 +k + 6k +6 \right] = \frac{(k+1)(k+2)(2k+3)}{6}$
6
This matches the required form for n=k+1, so P(k) → P(k+1), followed by the standard universal conclusion.

Exam tip:

Always expand the target RHS for n=k+1 first, then work backwards from the LHS to match it, to avoid getting stuck on messy algebra.

3. Induction for Divisibility Proofs★★★☆☆⏱ 6 min

Divisibility proofs require you to show a given expression f(n) is exactly divisible by a fixed integer d for all positive n. The standard technique rewrites f(k+1) in terms of f(k) plus a multiple of d.

📘 Definition

Divisibility Notation

$d ∣ f (n)$

The integer d divides f(n) exactly, with no remainder, so f(n) = d * m for some integer m.

📐 Worked Example

Prove that $7^{n} - 1$ is divisible by 6 for all positive integers n

1
Base case n=1: $7^{1} - 1 = 6$ , which is divisible by 6, so P(1) is true.
2
Inductive hypothesis: Assume $7^{k} - 1 = 6 m$ for some integer m.
3
Inductive step: Rewrite $7^{k + 1} - 1 = 7 \times 7^{k} - 1$
4
$= 7 \times (6m +1) -1 = 42m + 6 = 6(7m +1)$
5
This is a clear multiple of 6, so P(k+1) holds, followed by the standard conclusion.

4. Induction for Matrix Power Identities★★★★☆⏱ 7 min

Matrix induction proofs require you to prove that raising a given 2x2 or 3x3 matrix M to the power n produces a specified standard form matrix. The inductive step uses the identity $M^{k + 1} = M^{k} \times M$ .

📐 Worked Example

Prove that for $M = (1021)$ , $M^{n} = (10 2 n 1)$ for all positive integers n

1
Base case n=1: $M^{1} = M$ , which matches the RHS with 2*1=2, so P(1) is true.
2
Inductive hypothesis: Assume $M^{k} = (10 2 k 1)$
3
$M^{k+1} = M^k M = \begin{pmatrix} 1 & 2k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$
4
$= \begin{pmatrix} 1 & 2(k+1) \\ 0 & 1 \end{pmatrix}$
5
This matches the required form for n=k+1, so P(k) → P(k+1), followed by the standard conclusion.

5. Common Pitfalls

Wrong move:

Skipping the base case entirely to go straight to the inductive step

Why:

This creates a logical fallacy where you can prove false statements like 'all integers are equal', and you lose 2-3 easy marks

Correct move:

Always test n=1 (or the specified starting value) first, and state the result clearly.

Wrong move:

Writing 'assume P(n) is true' instead of 'assume P(k) is true'

Why:

This confuses the general variable with the specific fixed integer k used in the hypothesis, losing a communication mark

Correct move:

Explicitly define k as a positive integer for which P(k) is assumed true.

Wrong move:

Failing to explicitly state the final conclusion linking back to the induction principle

Why:

CIE mark schemes allocate a standalone 1 mark for this concluding statement, which is often missed by rushed students

Correct move:

End every proof with the standard line: 'Since P(1) is true, and P(k) true implies P(k+1) true, P(n) holds for all positive integers n'.

Wrong move:

In divisibility proofs, not defining the integer multiple (e.g. not stating $7^{k} - 1 = 6 m$ where m is an integer)

Why:

Examiners will deduct marks for not justifying that the resulting expression is a whole multiple of d

Correct move:

Explicitly name the integer multiple variable and state it is an integer.

Wrong move:

In matrix induction, multiplying $M \times M^{k}$ instead of $M^{k} \times M$

Why:

Matrix multiplication is not commutative, so this will produce an incorrect result for non-commuting matrices

Correct move:

Always write $M^{k + 1} = M^{k} \times M$ to match the inductive hypothesis structure.

6. Quick Reference Cheatsheet

Proof Type	Key Inductive Step Identity	Typical Mark Weight
Summation	$\sum_{r = 1}^{k + 1} f (r) = \sum_{r = 1}^{k} f (r) + f (k + 1)$	6-7 marks
Divisibility	$f (k + 1) = a f (k) + c d$	5-6 marks
Matrix Power	$M^{k + 1} = M^{k} M$	7-8 marks
Recurrence Relation	$u_{k + 1} = f (u_{k})$	6-7 marks

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2025 · 12
Prove 7^n -1 is divisible by 6
2024 · 11
Prove summation of r(r+1)
2023 · 13
Prove 2x2 matrix power identity

What's Next

You have now mastered the core structure and 3 most common induction proof types that appear in CIE 9231 Further Pure 1 exams. To reinforce your skills, practice full past-style induction questions that combine multiple concepts, including inequalities and recurrence relation proofs, which are the next level of difficulty for this topic. You can also review related proof methods including proof by contradiction, another frequently tested topic in Further Pure 1, to build a full toolkit of formal proof techniques for your exam. Mastering induction will also support you when you work on sequences and series proofs later in the syllabus.