What is not using the assumption?

The inductive step must use P(k) explicitly (substitute it in); a proof that re-derives P(k+1) from scratch is not a valid induction and scores no inductive-step marks.

What is vague divisibility?

Show the result is a clear integer multiple of the divisor (write it as divisor times an integer), not just assert it is "divisible".

What is wrong base case?

Start at the smallest value the statement claims, which is not always n = 1; check the question for n 0 or n 2.

Verify the base case for _r=1^n r^2 = (n(n+1)(2n+1))/(6). [2 marks]

Pearson Edexcel Edexcel 2018-style practice: Prove by induction that _r=1^n r(r+1) = (1)/(3)n(n+1)(n+2) for all positive integers n.

Run the three-part structure: base case, inductive step, conclusion. Base case n = 1: LHS = 1 · 2 = 2; RHS = (1)/(3)(1)(2)(3) = 2. True for n = 1 (B1). Assume true for n = k: _r=1^k r(r+1) = (1)/(3)k(k+1)(k+2) (M1 for stating the assumption). For n = k+1: _r=1^k+1 r(r+1) = (1)/(3)k(k+1)(k+2) + (k+1)(k+2) (M1). Factor out (k+1)(k+2): = (k+1)(k+2)[(k)/(3) + 1] = (k+1)(k+2)·(k+3)/(3) = (1)/(3)(k+1)(k+2)(k+3) (A1), which is the formula with k+1 (A1). Conclusion: true for n = 1 and, if true for k, true for k+1; so by induction true for all n 1 (A1 for the precise conclusion).

Pearson Edexcel Edexcel 2021-style practice: Prove by induction that f(n) = 5^n + 8n - 1 is divisible by 4 for all positive integers n.

Show divisibility by expressing f(k+1) in terms of f(k) plus a multiple of 4. Base case n = 1: f(1) = 5 + 8 - 1 = 12 = 4 × 3, divisible by 4 (B1). Assume f(k) = 5^k + 8k - 1 is divisible by 4 (M1). f(k+1) = 5^k+1 + 8(k+1) - 1 = 5· 5^k + 8k + 8 - 1 (M1). Write 5· 5^k = 5^k + 4· 5^k, so f(k+1) = (5^k + 8k - 1) + 4· 5^k + 8 = f(k) + 4(5^k + 2) (A1). Both f(k) (by assumption) and 4(5^k + 2) are divisible by 4, so f(k+1) is divisible by 4 (A1). By induction f(n) is divisible by 4 for all n 1 (A1 for conclusion).

Pearson Edexcel Edexcel 2023-style practice: The matrix M = pmatrix 2 & 0 \\ 1 & 1 pmatrix. Prove by induction that M^n = pmatrix 2^n & 0 \\ 2^n - 1 & 1 pmatrix for all positive integers n.

Verify the base case, then multiply the assumed M^k by M. Base case n = 1: the formula gives pmatrix 2 & 0 \\ 2 - 1 & 1 pmatrix = pmatrix 2 & 0 \\ 1 & 1 pmatrix = M. True (B1). Assume M^k = pmatrix 2^k & 0 \\ 2^k - 1 & 1 pmatrix (M1). Then M^k+1 = M^k M = pmatrix 2^k & 0 \\ 2^k - 1 & 1 pmatrixpmatrix 2 & 0 \\ 1 & 1 pmatrix = pmatrix 2^k+1 & 0 \\ 2(2^k - 1) + 1 & 1 pmatrix (M1 A1). The bottom-left is 2^k+1 - 2 + 1 = 2^k+1 - 1 (A1), giving the formula with k+1. By induction the result holds for all n 1 (A1 for conclusion).

EnglandFurther MathsSyllabus dot point

How does mathematical induction prove a statement for all positive integers?

The structure of proof by induction, applied to summation formulae, divisibility results, recurrence relations and powers of matrices, with rigorous base case, inductive step and conclusion.

A focused answer to the Edexcel A-Level Further Mathematics proof by induction content, covering the structure of an induction proof and its application to summation formulae, divisibility results, recurrence relations and powers of matrices, with the rigorous base case, inductive step and conclusion examiners reward.

Generated by Claude Opus 4.812 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The three-part structure
A summation proof
Divisibility and matrix powers
Examples in context
Try this

What this dot point is asking

Edexcel wants you to write rigorous proofs by induction: state and verify a base case, assume the statement for $n = k$ , use that assumption to prove it for $n = k + 1$ , and conclude precisely. The four standard targets are summation formulae, divisibility results, recurrence relations and powers of matrices. Induction appears on essentially every Core Pure paper, and the marks are spread across all three parts of the structure, so each part must be present and explicit.

The three-part structure

Every induction proof follows the same skeleton, and examiners award marks for each part separately. The single most common reason for losing marks is a missing or vague conclusion, so treat the conclusion as a fixed sentence you write at the end of every proof.

A summation proof

For a summation formula, the inductive step adds the $(k + 1)$ th term to the assumed sum, then rearranges to the formula with $k + 1$ substituted for $k$ . The reliable move is to factor out the common bracket before tidying.

Prove a summation formula

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

Step 1: Prove the base case

At $n = 1$ the left-hand side is the single term $1$ . The right-hand side gives $\dfrac{1 \cdot 2}{2} = 1$ . Both sides agree, so $P(1)$ is true.

Step 2: State the inductive hypothesis

Assume that for some positive integer $k$ the statement $P(k)$ holds:

\sum_{r=1}^{k} r = \frac{k(k+1)}{2}.

Step 3: Prove $P(k+1)$

We need to reach the $(k+1)$ th partial sum. Add the next term $(k+1)$ to both sides of the assumed identity, then factor out $(k+1)$ to recognise the formula at $k+1$ :

\sum_{r=1}^{k+1} r = \frac{k(k+1)}{2} + (k+1) = (k+1)\!\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}.

This is precisely the formula with $k + 1$ in place of $n$ , so $P(k+1)$ is true.

Step 4: State the conclusion

Since $P(1)$ is true and $P(k)$ being true implies $P(k+1)$ is true, by mathematical induction the result holds for all positive integers $n \ge 1$ .

Divisibility and matrix powers

For a divisibility proof, write the expression at $k + 1$ as the expression at $k$ plus a clear integer multiple of the divisor, so both pieces are divisible. For a matrix power, multiply the assumed $M^k$ by $M$ and simplify each entry to the conjectured form with exponent $k + 1$ .

Prove a divisibility result

Prove that $f(n) = 3^{2n} - 1$ is divisible by $8$ for all positive integers $n$ .

Step 1: Prove the base case

Evaluate $f(1) = 3^2 - 1 = 9 - 1 = 8 = 8 \times 1$ . Since $8$ is divisible by $8$ , $P(1)$ is true.

Step 2: State the inductive hypothesis

Assume $P(k)$ : $f(k) = 3^{2k} - 1$ is divisible by $8$ , so $f(k) = 8q$ for some integer $q$ .

Step 3: Prove $P(k+1)$

We write $f(k+1)$ in terms of $f(k)$ by factoring out $9 = 3^2$ . Adding and subtracting $9$ achieves this:

f(k+1) = 3^{2(k+1)} - 1 = 9 \cdot 3^{2k} - 1 = 9(3^{2k} - 1) + 9 - 1 = 9\,f(k) + 8.

By the inductive hypothesis $f(k)$ is divisible by $8$ , so $9\,f(k)$ is divisible by $8$ . The term $8$ is plainly divisible by $8$ . Their sum $f(k+1)$ is therefore divisible by $8$ .

Step 4: State the conclusion

Since $P(1)$ is true and $P(k)$ being true implies $P(k+1)$ is true, by mathematical induction $3^{2n} - 1$ is divisible by $8$ for all positive integers $n \ge 1$ .

Examples in context

Induction underpins much of the rest of Core Pure. It is the rigorous justification for the standard summation results $\sum r$ , $\sum r^2$ and $\sum r^3$ used in further algebra, and for closed forms of recurrence relations. The matrix-power proofs link directly to the matrices dot point, where you first conjecture $M^n$ by computing $M^2$ and $M^3$ and spotting the pattern, then prove it. De Moivre's theorem $(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta$ is itself proved by induction for positive integers $n$ , connecting induction to complex numbers. Whenever a result is claimed "for all $n$ ", induction is the default tool.

Try this

Q1. Verify the base case for $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$ . [2 marks]

Cue. At $n = 1$ the sum is $1$ and the formula gives $\frac{1 \cdot 2 \cdot 3}{6} = 1$ .

Q2. State the assumption you make in the inductive step. [1 mark]

Cue. Assume the statement $P(k)$ is true for some positive integer $k$ .

Q3. In a divisibility proof, you reach $f(k+1) = 7f(k) + 36$ where the divisor is $6$ . Complete the argument. [2 marks]

Cue. $7f(k)$ is divisible by $6$ (as $f(k)$ is, by assumption) and $36 = 6 \times 6$ , so $f(k+1)$ is divisible by $6$ .

Exam-style practice questions

Practice questions written in the style of Pearson Edexcel exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Edexcel 20186 marksProve by induction that

\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)

for all positive integers

n

Show worked answer →

Run the three-part structure: base case, inductive step, conclusion.

Base case $n = 1$ : LHS $= 1 \cdot 2 = 2$ ; RHS $= \frac{1}{3}(1)(2)(3) = 2$ . True for $n = 1$ (B1).

Assume true for $n = k$ : $\sum_{r=1}^{k} r(r+1) = \frac{1}{3}k(k+1)(k+2)$ (M1 for stating the assumption).

For $n = k+1$ : $\sum_{r=1}^{k+1} r(r+1) = \frac{1}{3}k(k+1)(k+2) + (k+1)(k+2)$ (M1). Factor out $(k+1)(k+2)$ : $= (k+1)(k+2)\left[\frac{k}{3} + 1\right] = (k+1)(k+2)\cdot\frac{k+3}{3} = \frac{1}{3}(k+1)(k+2)(k+3)$ (A1), which is the formula with $k+1$ (A1).

Conclusion: true for $n = 1$ and, if true for $k$ , true for $k+1$ ; so by induction true for all $n \ge 1$ (A1 for the precise conclusion).

Edexcel 20216 marksProve by induction that

f(n) = 5^n + 8n - 1

is divisible by

4

for all positive integers

n

Show worked answer →

Show divisibility by expressing $f(k+1)$ in terms of $f(k)$ plus a multiple of $4$ .

Base case $n = 1$ : $f(1) = 5 + 8 - 1 = 12 = 4 \times 3$ , divisible by $4$ (B1).

Assume $f(k) = 5^k + 8k - 1$ is divisible by $4$ (M1).

$f(k+1) = 5^{k+1} + 8(k+1) - 1 = 5\cdot 5^k + 8k + 8 - 1$ (M1). Write $5\cdot 5^k = 5^k + 4\cdot 5^k$ , so $f(k+1) = (5^k + 8k - 1) + 4\cdot 5^k + 8 = f(k) + 4(5^k + 2)$ (A1).

Both $f(k)$ (by assumption) and $4(5^k + 2)$ are divisible by $4$ , so $f(k+1)$ is divisible by $4$ (A1). By induction $f(n)$ is divisible by $4$ for all $n \ge 1$ (A1 for conclusion).

Edexcel 20236 marksThe matrix

M = \begin{pmatrix} 2 & 0 \\ 1 & 1 \end{pmatrix}

. Prove by induction that

M^n = \begin{pmatrix} 2^n & 0 \\ 2^n - 1 & 1 \end{pmatrix}

for all positive integers

n

Show worked answer →

Verify the base case, then multiply the assumed $M^k$ by $M$ .

Base case $n = 1$ : the formula gives $\begin{pmatrix} 2 & 0 \\ 2 - 1 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 1 & 1 \end{pmatrix} = M$ . True (B1).

Assume $M^k = \begin{pmatrix} 2^k & 0 \\ 2^k - 1 & 1 \end{pmatrix}$ (M1).

Then $M^{k+1} = M^k M = \begin{pmatrix} 2^k & 0 \\ 2^k - 1 & 1 \end{pmatrix}\begin{pmatrix} 2 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 2^{k+1} & 0 \\ 2(2^k - 1) + 1 & 1 \end{pmatrix}$ (M1 A1). The bottom-left is $2^{k+1} - 2 + 1 = 2^{k+1} - 1$ (A1), giving the formula with $k+1$ .

By induction the result holds for all $n \ge 1$ (A1 for conclusion).

Related dot points

Sources & how we know this

Pearson Edexcel A-Level Further Mathematics (9FM0) specification — Pearson Edexcel (2017)