Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn7367Paper 1 · Compulsory contentProofProof by induction

Proof · Subtopic 1 of 1

Proof by Induction

Show a statement is true for $n=1$ , then show that if it is true for $n=k$ it must be true for $n=k+1$ . Together these prove it for every positive integer, like an endless line of falling dominoes.

Cambridge 9231 Paper 1Edexcel YFM01 WFM01Edexcel 9FM0 Paper 1Edexcel 9FM0 Paper 2AQA 7367 Paper 1AQA 7367 Paper 2≈ 40 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

State the four parts of an induction proof: basis, assumption, inductive step, conclusion.
Prove formulae for sums of series by induction.
Prove divisibility results by induction.
Prove results about powers of matrices and recurrence relations.

Pause and think

You check that $1+3+5+\cdots+(2n-1)=n^2$ for $n=1,2,\ldots,1000$ on a computer. Is that a proof?

Section 2 of 14

Core idea

Start hereAn endless line of dominoes

Imagine infinitely many dominoes in a row. You can't push them all, but you don't need to. If you knock the first one over, and you know every domino knocks over the next one, then every domino falls. That's proof by induction: one check plus one general argument covers infinitely many cases.

The big idea

To prove $P(n)$ for all positive integers $n$ : (1) show $P(1)$ is true; (2) assume $P(k)$ is true; (3) use it to show $P(k+1)$ is true; (4) conclude.

1. The four parts

Structure of every induction proof

Drawing diagram…

The conclusion sentence earns its own mark.

P(1)\ \wedge\ \bigl(P(k)\Rightarrow P(k+1)\bigr)\ \Longrightarrow\ P(n)\ \forall n\in\mathbb Z^+

$P(n)$: the statement for the integer $n$ .
$\Rightarrow$: "implies".
$\mathbb Z^+$: positive integers.

Key takeawayWhy it works

P(1)

true gives

P(2)

;

P(2)

gives

P(3)

; and so on. No positive integer is ever skipped.

2. Sums of series

Proving

\sum_{r=1}^n r=\tfrac12n(n+1)

$n=1:\ \text{LHS}=1,\ \text{RHS}=\tfrac12(1)(2)=1$
Basis: both sides agree.
$\sum_{r=1}^k r=\tfrac12k(k+1)$
Assume true for $n=k$ .
$\text{Target: }\sum_{r=1}^{k+1}r=\tfrac12(k+1)(k+2)$
Write $P(k+1)$ before starting.
$\sum_{r=1}^{k+1}r=\tfrac12k(k+1)+(k+1)$
The first $k$ terms, plus the $(k+1)$ th term.
$=\tfrac12(k+1)(k+2)$
Factor out $\tfrac12(k+1)$ : $\tfrac12(k+1)[k+2]$ .

This is the target, so

P(k)\Rightarrow P(k+1)

. Conclude.

Worked exampleSum of squares

Prove $\displaystyle\sum_{r=1}^n r^2=\tfrac16n(n+1)(2n+1)$ .

Goal: Induction proof.
Strategy: Add the $(k+1)$ th term, take out the common factor $\tfrac16(k+1)$ , factorise towards the target.

$n=1:\ 1=\tfrac16(1)(2)(3)$
Basis.
$\sum_{r=1}^{k+1}r^2=\tfrac16k(k+1)(2k+1)+(k+1)^2$
Assumption plus next term.
$=\tfrac16(k+1)\left[k(2k+1)+6(k+1)\right]$
Common factor; $(k+1)^2=\tfrac16(k+1)\cdot6(k+1)$ .
$=\tfrac16(k+1)(2k^2+7k+6)=\tfrac16(k+1)(k+2)(2k+3)$
Expand and factorise.

Answer

\tfrac16(k+1)\bigl((k+1)+1\bigr)\bigl(2(k+1)+1\bigr)

: the formula with

n=k+1

. True for all

n\in\mathbb Z^+

✓ Check

n=3

1+4+9=14

and

\tfrac16(3)(4)(7)=14

✓.

3. Divisibility

The key move:

f(k+1)

in terms of

f(k)

$f(n)=5^n+3$
Claim: divisible by 4.
$f(k+1)-5f(k)=5^{k+1}+3-5^{k+1}-15$
Multiply by 5 so the powers cancel.
$=-12$
A multiple of 4.
$f(k+1)=5f(k)-12$
Both terms are divisible by 4 if $f(k)$ is.

With

f(1)=8

, the result holds for all

n

Worked example $7^n-1$ is divisible by 6

Prove for all positive integers $n$ .

Goal: Induction proof.
Strategy: Compare $f(k+1)$ with $7f(k)$ .

$f(1)=6$
Basis: $6\mid6$ .
$f(k+1)-7f(k)=7^{k+1}-1-7^{k+1}+7=6$
Powers cancel.
$f(k+1)=7f(k)+6$
Both terms divisible by 6.

AnswerIf

6\mid f(k)

then

6\mid f(k+1)

; true for

n=1

; so true for all

n

✓ Check

f(2)=48=6\times8

✓.

TrickChoosing the multiplier Multiply

f(k)

by the base of the power (

5

7

, …) so the highest powers cancel.

4. Matrices and sequences

Worked exampleA matrix power

Prove $\begin{pmatrix}1&2\\0&1\end{pmatrix}^n=\begin{pmatrix}1&2n\\0&1\end{pmatrix}$ .

Goal: Induction proof.
Strategy: $\mathbf M^{k+1}=\mathbf M^k\mathbf M$ .

$n=1:\ \begin{pmatrix}1&2\\0&1\end{pmatrix}$
Basis.
$\mathbf M^{k+1}=\begin{pmatrix}1&2k\\0&1\end{pmatrix}\begin{pmatrix}1&2\\0&1\end{pmatrix}$
Assumption times $\mathbf M$ .
$=\begin{pmatrix}1&2+2k\\0&1\end{pmatrix}=\begin{pmatrix}1&2(k+1)\\0&1\end{pmatrix}$
Multiply.

AnswerTrue for

n=k+1

; conclude for all

n

✓ Check

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

by direct multiplication ✓.

Worked exampleA recurrence relation

$u_1=2$ , $u_{n+1}=3u_n-2$ . Prove $u_n=3^{n-1}+1$ .

Goal: Induction proof.
Strategy: Substitute the assumption into the recurrence.

$u_1=3^0+1=2$
Basis.
$u_{k+1}=3(3^{k-1}+1)-2$
Recurrence with the assumption.
$=3^k+1=3^{(k+1)-1}+1$
Simplify: the formula with $n=k+1$ .

AnswerTrue for all

n

✓ Check

u_2=4=3^1+1

✓.

Common misconceptionAssuming the answer Never start from

P(k+1)

and "work back": that assumes what you're proving. Start from

P(k)

Edge caseStarting later

2^n>n^2

fails for

n=2,3,4

but holds from

n=5

. Use basis

n=5

and conclude "for all

n\ge5

Pause and think

What goes wrong in "proving" every horse is the same colour by induction?

Summary

Basis, assumption, inductive step, conclusion.
Series: add the next term and factorise.
Divisibility: $f(k+1)-mf(k)$ .
Matrices: $\mathbf M^{k+1}=\mathbf M^k\mathbf M$ .

Basis: The first case, checked directly.
Inductive step: Showing $P(k)\Rightarrow P(k+1)$ .

HistoryPascal and Maurolico. Francesco Maurolico used an induction-style argument in 1575 to prove that the sum of the first

n

odd numbers is

n^2

. Blaise Pascal used it clearly in his 1654 work on the arithmetic triangle.

Fun factThe domino record. The world record domino topple has over four million dominoes. Each one only needs to knock over the next, which is exactly the inductive step.

Section 3 of 14

Key formulae

Structure

P(1)\ \text{true},\quad P(k)\Rightarrow P(k+1)\quad\Longrightarrow\quad P(n)\ \text{true for all } n\in\mathbb Z^+

Divisibility trick

f(k+1)-mf(k)=\text{(multiple of the divisor)}

TrickAim for the target. Before you start the inductive step, write down what

P(k+1)

says. Then you always know what you are trying to reach, and the algebra has a destination.

Section 4 of 14

Worked examples

Example 1 · A sum0 / 4 steps

Prove that

\displaystyle\sum_{r=1}^n r^2=\tfrac16n(n+1)(2n+1)

Example 2 · Divisibility0 / 4 steps

Prove that

f(n)=5^n+3

is divisible by

4

for all positive integers

n

Section 5 of 14

Explore the graph

Sum of the first n odd numbers

Loading the interactive graph…

Try this

The point is $(n,1+3+\cdots+(2n-1))$ . Why does it always sit on $y=x^2$ ?
Moving from $n$ to $n+1$ adds the next odd number $2n+1$ . Check $n^2+(2n+1)=(n+1)^2$ .

Each step adds $2n+1$ , exactly the gap between consecutive squares: that is the inductive step.

In the real worldChecking computer programs. Software that loops is proved correct with a "loop invariant": show it holds before the loop, and that one pass keeps it true. That is induction, and it is used to verify code in aircraft and chips.

Section 6 of 14

Common mistakes

IncorrectProving only

n=1,2,3

CorrectProve

P(k)\Rightarrow P(k+1)

for general

k

Examples never cover every case.

IncorrectAssuming

P(k+1)

and working backwards

CorrectStart from

P(k)

and reach

P(k+1)

Assuming what you want to prove is circular.

IncorrectLeaving out the conclusion

CorrectState: true for

n=1

and

P(k)\Rightarrow P(k+1)

, so true for all

n

Mark schemes give a mark for the full conclusion.

Me: true for n = 1, 2, 3, 4…

Induction: just knock over the first domino and prove each one topples the next. 😎

Section 7 of 14

Exam tip

Exam tipWrite P(k + 1) first. Writing the target statement (with

k+1

in place of

n

) at the start of the inductive step shows the examiner where you are heading, and helps you factorise towards it.

Section 8 of 14

Guided practice

SA-FP-IND-G012 marksL2 StandardNon-calculatorSeries

In proving

\displaystyle\sum_{r=1}^n r(r+1)=\tfrac13n(n+1)(n+2)

, the sum to

k+1

terms is

\tfrac13k(k+1)(k+2)+(k+1)(k+2)

. This factorises to

\tfrac13(k+1)(k+2)(k+a)

. Find

a

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-FP-IND-0012 marksL2 StandardNon-calculatorDivisibility

Let

f(n)=7^n-1

. Find the constant

c

such that

f(k+1)-7f(k)=c

Salam Academy Original Practice · Proposed mark scheme

SA-FP-IND-0021 markL1 FoundationNon-calculatorDivisibility

To prove

3^{2n}+11

is divisible by

4

, first check

n=1

. Find

3^{2}+11

Salam Academy Original Practice · Proposed mark scheme

SA-FP-IND-0032 marksL2 StandardNon-calculatorMatrices and sequences

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

and it can be proved that

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

. Find the top-right entry of

\mathbf M^5

Salam Academy Original Practice · Proposed mark scheme

SA-FP-IND-0042 marksL2 StandardNon-calculatorMatrices and sequences

A sequence has

u_1=2

and

u_{n+1}=3u_n-2

. It can be proved that

u_n=3^{n-1}+1

. Find

u_4

Salam Academy Original Practice · Proposed mark scheme

SA-FP-IND-0052 marksL1 FoundationCalculatorSeries

Given

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

, evaluate

\displaystyle\sum_{r=1}^{10} r^3

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-FP-IND-0062 marksL4 ChallengingNon-calculatorMatrices and sequences

The statement

2^n>n^2

is to be proved by induction for all integers

n\ge n_0

. Find the smallest

n_0\ge3

for which the basis case is true.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Basis: show $P(1)$ .
Assume $P(k)$ ; deduce $P(k+1)$ .
Divisibility: write $f(k+1)$ in terms of $f(k)$ .
Always finish with the full conclusion.

Section 12 of 14

Quick quiz

Q1 · SA-FP-IND-Q011 markL1 FoundationNon-calculatorSeries

In an induction proof, which step uses the assumption?

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: 7367 A-level Further Mathematics
Where: Paper 1 and 2 · Proof
Expected: Prove by induction, including sums, divisibility and matrix powers.
Calculator: Permitted on all papers.
Typical style: AQA mixes short multiple-choice questions with longer structured ones.
Open in: 7367 · Paper 1 7367 · Paper 2

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: AQA 7367, First teaching 2017 (official specification).