Notes · Further MathematicsUK · A-Levels

Proof

Further Mathematics adds proof by mathematical induction to the deduction, exhaustion, counter-example and contradiction methods met in A-Level Mathematics. Induction is the standard tool for proving results that are indexed by a positive integer $n$ : summation formulae, divisibility statements and formulae for powers of matrices. The emphasis throughout is on a complete, correctly structured argument, since the reasoning objective (AO2) carries even more weight here than in the single Mathematics A-Level.

5 sections~16 min reading time3 competenciesLevel Standard 3 · Advanced 2

T·0111 / 13

Exam profile

AO2 · Construct and present a rigorous mathematical argument, laying out the base case, inductive step and conclusion explicitlyAO1 · Carry out accurately the algebraic manipulation demanded inside the inductive stepAO3 · Select mathematical induction as the appropriate strategy and structure a complete multi-step proof

Operators:proveprove by inductionshow thatdeducehencestate

basic level

AS Further Mathematics expects induction for the summation of standard series and for straightforward divisibility results, with the three-part structure clearly shown.

higher level

The full A-Level extends induction to powers of matrices, to sequences defined by a recurrence, and to results combined with complex numbers or calculus, and it examines the precise logical wording of the conclusion.

Depth

Text

Contents · 5 sections

Proof

The principle of mathematical induction#

StandardAQA 7367 §3.1DfE Further Mathematics — Proof

The induction domino chain

Fig. 1The base case topples the first domino; the inductive step guarantees each domino topples the next, so all fall.

Mathematical induction proves that a statement

P(n)

is true for every integer

n

from some starting value onwards (usually

n \geq 1

). It rests on a single idea: if the statement is true for a first value, and if its truth at any value forces its truth at the next value, then it must be true for all of them. The standard image is a line of dominoes — knock over the first and arrange that each falling domino topples the next, and every domino falls. The falling of the first domino is the base case; the arrangement that each topples the next is the inductive step.

A proof by induction therefore has three compulsory parts, and marks are lost whenever one is missing or sloppy. First, the base case: show directly that

P(1)

(or whatever the first value is) holds, by substituting it into both sides. Second, the inductive step: assume that

P(k)

is true for some particular integer

k

— this is the inductive hypothesis — and use it to prove

P(k+1)

. Third, the conclusion: state that since

P(1)

is true and

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

, by the principle of mathematical induction

P(n)

is true for all

n \geq 1

The logical engine is the implication

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

, established for a general

k

. Note carefully what is and is not assumed: you assume

P(k)

for one unspecified value

k

, not for all values (that would be assuming what you are trying to prove). The whole force of the method is that a single general implication, together with one concrete starting case, delivers infinitely many statements at once. This is genuinely different from checking cases: verifying

P(1), P(2), P(3)

proves nothing about

P(100)

, whereas a valid inductive step proves them all.

Induction is the natural tool whenever a claim is indexed by a positive integer and each case is built from the previous one. That covers the three families examined at A-Level: closed formulae for finite sums

\sum_{r=1}^{n} f(r)

, divisibility statements such as '

f(n)

is divisible by

m

for all

n

', and formulae for the

n

th power

\mathbf{M}^n

of a square matrix. In each family the inductive step has a characteristic move — split off the last term, factor out a common divisor, or multiply by one more copy of

\mathbf{M}

— which is worth learning as a template.

\big[\,P(1)\ \text{true}\,\big]\ \wedge\ \big[\,\forall k\ \big(P(k)\Rightarrow P(k+1)\big)\,\big]\ \Longrightarrow\ \forall n\geq 1,\ P(n)

The principle of mathematical induction

A true base case together with the general implication $P(k)\Rightarrow P(k+1)$ yields the truth of $P(n)$ for every integer $n\geq 1$ .

Worked example

The structure on a first example

Prove by induction that $\sum_{r=1}^{n} r = \tfrac{1}{2}n(n+1)$ for all integers $n \geq 1$ .

Base case
For $n=1$ the left-hand side is $1$ and the right-hand side is $\tfrac{1}{2}(1)(2)=1$ . They agree, so $P(1)$ is true.
Inductive hypothesis
Assume the result holds for $n=k$ , i.e. $\sum_{r=1}^{k} r = \tfrac{1}{2}k(k+1)$ .
Inductive step
Add the next term $(k+1)$ to both sides: $\sum_{r=1}^{k+1} r = \tfrac{1}{2}k(k+1) + (k+1) = (k+1)\big(\tfrac{1}{2}k + 1\big) = \tfrac{1}{2}(k+1)(k+2)$ .
$\sum_{r=1}^{k+1} r = \tfrac{1}{2}(k+1)\big((k+1)+1\big)$
Conclusion
This is exactly $P(k+1)$ . Since $P(1)$ is true and $P(k)\Rightarrow P(k+1)$ , by induction the result holds for all $n\geq 1$ .

Result: $\sum_{r=1}^{n} r = \tfrac{1}{2}n(n+1)$ for all integers $n\geq 1$ .

Typical mistakes

Omitting the base case, or checking it only informally — without $P(1)$ the chain of implications never starts and the proof is worthless.
Writing 'assume it is true for all $k$ ', which assumes the very statement to be proved; the hypothesis is about a single value $k$ .

Active revision

Explain, in your own words and with reference to the domino image, why an inductive step $P(k)\Rightarrow P(k+1)$ on its own is not enough to prove $P(n)$ for all $n$ , and why a base case on its own is likewise insufficient.

Active recall

Recall the key points — then reveal.

Sources: Further mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Further Mathematics 7367 specification (AQA)

Induction for the summation of series#

StandardAQA 7367 §3.1DfE Further Mathematics — Proof

The commonest use of induction is to prove a closed formula for a finite sum

\sum_{r=1}^{n} f(r)

. The inductive step has a fixed shape: start from the assumed sum to

k

terms, add the single term

f(k+1)

, and rearrange the result into the target formula with

k+1

in place of

n

. Almost all the work is algebraic — the skill is factorising cleanly rather than expanding everything and hoping.

The decisive tactic is to take out the common factor early. When proving

\sum_{r=1}^{n} r^2 = \tfrac{1}{6}n(n+1)(2n+1)

, after adding

(k+1)^2

you should immediately extract the factor

(k+1)

that the target answer must contain, leaving

\tfrac{1}{6}(k+1)\big[k(2k+1) + 6(k+1)\big]

. Expanding only the bracket gives

2k^2+7k+6 = (k+2)(2k+3)

, and the target form

\tfrac{1}{6}(k+1)(k+2)(2k+3)

appears without a messy cubic ever being written out. Recognising the required factors in advance turns a daunting expansion into a short one.

These proofs justify the standard results that are then quoted freely in the Further Algebra topic:

\sum r = \tfrac{1}{2}n(n+1)

\sum r^2 = \tfrac{1}{6}n(n+1)(2n+1)

and

\sum r^3 = \tfrac{1}{4}n^2(n+1)^2 = \big(\sum r\big)^2

. It is worth noticing the elegant fact that the sum of the first

n

cubes equals the square of the sum of the first

n

integers; this is exactly the kind of surprising identity that induction confirms cleanly even when it gives no hint as to why it is true.

A subtle point of rigour is that the inductive step must reach the target formula identically, not merely to a number that happens to match for small

k

. Always finish by writing the right-hand side in the same functional form as

P(n)

but with

n

replaced by

k+1

, and say so; that sentence is what earns the AO2 marks and demonstrates that you have proved the general implication rather than checked another case.

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

Sum of the first n integers

The arithmetic-series result, provable by induction.

\sum_{r=1}^{n} r^2 = \tfrac{1}{6}n(n+1)(2n+1)

Sum of the first n squares

Proved by induction; quoted throughout Further Algebra.

\sum_{r=1}^{n} r^3 = \tfrac{1}{4}n^2(n+1)^2 = \left(\sum_{r=1}^{n} r\right)^2

Sum of the first n cubes

The sum of the first $n$ cubes is the square of the sum of the first $n$ integers.

Worked example

Sum of squares by induction

Prove by induction that $\displaystyle\sum_{r=1}^{n} r^2 = \tfrac{1}{6}n(n+1)(2n+1)$ for all integers $n\geq 1$ .

Base case
For $n=1$ : LHS $=1^2=1$ ; RHS $=\tfrac{1}{6}(1)(2)(3)=1$ . So $P(1)$ holds.
Hypothesis
Assume $\sum_{r=1}^{k} r^2 = \tfrac{1}{6}k(k+1)(2k+1)$ .
Add the next term
$\sum_{r=1}^{k+1} r^2 = \tfrac{1}{6}k(k+1)(2k+1) + (k+1)^2 = \tfrac{1}{6}(k+1)\big[k(2k+1) + 6(k+1)\big]$ .
$\tfrac{1}{6}(k+1)\big[\,k(2k+1)+6(k+1)\,\big]$
Factorise the bracket
$k(2k+1)+6(k+1) = 2k^2+7k+6 = (k+2)(2k+3)$ , so the sum is $\tfrac{1}{6}(k+1)(k+2)(2k+3)$ .
Match the target
This is $\tfrac{1}{6}(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)$ — exactly $P(k+1)$ . By induction the result holds for all $n\geq 1$ .

Result: $\displaystyle\sum_{r=1}^{n} r^2 = \tfrac{1}{6}n(n+1)(2n+1)$ for all integers $n\geq 1$ .

Typical mistakes

Expanding everything into an unfactorised polynomial and then being unable to recognise the target form; take the common factor out first.
Forgetting to add the $(k+1)$ th term (or adding the wrong term $f(k)$ again), so the step proves nothing.

Active revision

Prove by induction that $\sum_{r=1}^{n} r(r+1) = \tfrac{1}{3}n(n+1)(n+2)$ for all integers $n\geq 1$ .

Active recall

Recall the key points — then reveal.

Sources: Further mathematics: AS and A level content (GCE subject content) (Department for Education)

Induction for divisibility results#

AdvancedAQA 7367 §3.1DfE Further Mathematics — Proof

A divisibility proof shows that some expression

f(n)

is a multiple of a fixed integer

m

for all

n

. The inductive hypothesis is written as

f(k) = m\,t

for some integer

t

(i.e.

m

divides

f(k)

). The step then examines

f(k+1)

and manipulates it until a factor of

m

is visible, usually by writing

f(k+1)

in terms of

f(k)

The characteristic algebraic move is to form the difference or a suitable combination

f(k+1) - a\,f(k)

and show it is a multiple of

m

; then

f(k+1) = a\,f(k) + (\text{multiple of } m)

, and since

f(k)

is a multiple of

m

by hypothesis, so is

f(k+1)

. Choosing the multiplier

a

well is the whole art: it is picked so that the leading exponential or power terms cancel, leaving only multiples of

m

behind.

As a worked template, consider proving that

8 \mid 3^{2n} - 1

. Here

f(n)=3^{2n}-1 = 9^n - 1

. Then

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

. The term

9\,f(k)

is a multiple of

8

by the hypothesis, and

8

is obviously a multiple of

8

, so

f(k+1)

is a multiple of

8

. This single line — expressing

f(k+1)

as a known multiple plus an obvious multiple — is the heart of every divisibility induction.

Rigour requires that the integer

t

be named and its integer status respected: writing

f(k) = 8t

with

t\in\mathbb{Z}

makes it legitimate to conclude

f(k+1) = 8(9t+1)

with

9t+1

an integer, hence a genuine multiple of

8

. Do not leave the divisor implicit; state it, and finish by observing that the base case

f(1)

is divisible by

m

so the chain is grounded.

f(k+1) = a\,f(k) + m\,c \quad\Rightarrow\quad m \mid f(k+1)

The divisibility step

If $f(k)$ is a multiple of $m$ and $f(k+1)-a\,f(k)$ is a multiple of $m$ , then $f(k+1)$ is a multiple of $m$ .

Worked example

Divisibility by 8

Prove by induction that $3^{2n} - 1$ is divisible by $8$ for all integers $n\geq 1$ .

Base case
For $n=1$ : $3^{2} - 1 = 9-1 = 8 = 8\times 1$ , which is divisible by $8$ .
Hypothesis
Assume $3^{2k} - 1 = 8t$ for some integer $t$ ; equivalently $9^k - 1 = 8t$ .
Consider n = k+1
$3^{2(k+1)} - 1 = 9^{k+1} - 1 = 9\cdot 9^{k} - 1 = 9\,(9^{k} - 1) + 8 = 9(8t) + 8$ .
$9^{k+1}-1 = 9\,(9^{k}-1) + 8$
Extract the factor 8
$= 8(9t) + 8 = 8(9t + 1)$ , and $9t+1$ is an integer, so $3^{2(k+1)}-1$ is divisible by $8$ .
Conclusion
The base case holds and $P(k)\Rightarrow P(k+1)$ , so by induction $8 \mid 3^{2n}-1$ for all $n\geq 1$ .

Result: $3^{2n} - 1$ is divisible by $8$ for every integer $n\geq 1$ .

Typical mistakes

Verifying divisibility for a few values of $n$ and calling it a proof — that establishes nothing in general.
Manipulating $f(k+1)$ without ever using the hypothesis, so the multiple of $m$ from $f(k)$ is never brought in.

Active revision

Prove by induction that $3^{2n+2} - 8n - 9$ is divisible by $64$ for all integers $n\geq 1$ .

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

Induction for matrix powers and recurrences#

AdvancedAQA 7367 §3.1DfE Further Mathematics — Proof

The three-part structure of an inductive proof

Fig. 2Every induction proof flows through these three stages; the conclusion cites both the base case and the implication.

Induction also proves closed formulae for the

n

th power of a matrix,

\mathbf{M}^n

. The inductive step uses

\mathbf{M}^{k+1} = \mathbf{M}^{k}\,\mathbf{M}

(or

\mathbf{M}\,\mathbf{M}^{k}

): substitute the assumed form of

\mathbf{M}^{k}

and multiply by one further copy of

\mathbf{M}

, then simplify to the target form with

k+1

in place of

n

. Because matrix multiplication is not commutative, keep the copies of

\mathbf{M}

in the correct order.

A clean example is the shear-type matrix

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

, for which the claim is

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

. Multiplying the assumed

\mathbf{M}^k

\mathbf{M}

gives

\begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix}

, exactly the target. This connects directly to the Matrices topic, where

\mathbf{M}

represents a horizontal shear and

\mathbf{M}^n

the shear repeated

n

times.

The same structure handles sequences defined by a recurrence relation. If

u_{n+1}

is defined in terms of

u_n

and a closed formula for

u_n

is conjectured, induction verifies it: assume the formula at

n=k

, substitute into the recurrence to compute

u_{k+1}

, and show the result matches the formula at

n=k+1

. This is how one confirms, for instance, that a first-order linear recurrence has the closed form suggested by computing a few terms.

In every matrix or recurrence induction the base case must be checked for the actual matrix or first term (compute

\mathbf{M}^1

u_1

), not merely asserted; a formula that is off by a constant will still pass a lazy step but will fail the honest base case. This is one reason the base case is never a formality — it is the anchor that a correct step alone cannot supply.

\mathbf{M}^{k+1} = \mathbf{M}^{k}\,\mathbf{M}

The matrix-power step

Peel off one factor of $\mathbf{M}$ ; substitute the assumed $\mathbf{M}^{k}$ and multiply. Order matters — matrices do not commute.

Worked example

The nth power of a shear matrix

Given $\mathbf{M} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ , prove by induction that $\mathbf{M}^{n} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ for all integers $n\geq 1$ .

Base case
For $n=1$ , $\mathbf{M}^{1} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ , which matches the formula with $n=1$ .
Hypothesis
Assume $\mathbf{M}^{k} = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}$ .
Inductive step
$\mathbf{M}^{k+1} = \mathbf{M}^{k}\mathbf{M} = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix}$ .
$\mathbf{M}^{k+1} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix}$
Conclusion
This is the formula with $n=k+1$ . Since the base case holds and $P(k)\Rightarrow P(k+1)$ , by induction $\mathbf{M}^{n} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ for all $n\geq 1$ .

Result: $\mathbf{M}^{n} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ , the $n$ -fold shear.

Typical mistakes

Multiplying the matrices in the wrong order, or slipping into treating them as commuting numbers.
Skipping the base case computation $\mathbf{M}^1$ or $u_1$ , which is where an off-by-one error would surface.

Active revision

The matrix $\mathbf{A} = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}$ . Conjecture a formula for $\mathbf{A}^n$ and prove it by induction.

Active recall

Recall the key points — then reveal.

Sources: Further mathematics: AS and A level content (GCE subject content) (Department for Education)

Induction within the wider proof landscape#

StandardAQA 7367 §3.1DfE Further Mathematics — Proof

Induction sits alongside the proof methods already met in A-Level Mathematics, and part of the skill is choosing the right one. Direct proof (deduction) chains implications from the hypotheses to the conclusion; proof by exhaustion checks a claim over a finite, complete set of cases; disproof by counter-example refutes a universal claim with a single instance; and proof by contradiction assumes the negation and derives an impossibility (recap). Induction is specifically for statements indexed by an integer, where each case builds on the previous — it is the wrong tool for a one-off algebraic identity, which a direct proof handles better.

It helps to know induction's limits. It proves statements of the form 'for all integers

n\geq n_0

'; it cannot prove a statement about the real numbers as a whole, nor a claim with no natural integer index. When a claim genuinely depends on an earlier case that is not simply the immediately preceding one, a stronger form — 'strong' or 'complete' induction, where you assume

P(1),\dots,P(k)

all hold — is used; the base and conclusion are structured identically, only the hypothesis is broader.

A famous cautionary example shows why the base case matters: the 'proof' that all horses are the same colour has a flawless-looking inductive step but a broken link at

n=1\to 2

, and its false conclusion traces exactly to that gap. The lesson is that a slick step never compensates for an unverified or non-existent base, and that each implication in the chain — including the very first — must genuinely hold.

Finally, Further Mathematics rewards writing proofs as connected English-and-symbol arguments, not as isolated lines of algebra. State what you are assuming, flag where the hypothesis is used, and end with a sentence of conclusion. Because AO2 (reasoning and proof) carries more weight in Further Mathematics than in the single Mathematics A-Level, the difference between a complete and an incomplete argument is often the difference between full and partial marks.

\text{Strong induction:}\quad \big[P(1)\wedge\dots\wedge P(k)\big]\Rightarrow P(k+1)

Strong (complete) induction

The hypothesis assumes all cases up to $k$ ; useful when $P(k+1)$ depends on more than the immediately preceding case.

Worked example

Choosing a method: disproof by counter-example

Decide whether the statement 'for all integers $n\geq 1$ , $n^2 + n + 41$ is prime' is true, justifying your decision.

Recognise the claim type
This is a universal claim over the integers. A single counter-example would disprove it; no amount of confirming cases would prove it, so induction is not the tool for a false claim.
Search for a counter-example
The expression is prime for many small $n$ , which is a trap. Try $n=40$ : $40^2 + 40 + 41 = 1600 + 40 + 41 = 1681$ .
Show it is composite
$1681 = 41^2$ , since $41\times 41 = 1681$ . So $n=40$ gives a value with the factor $41$ , which is not prime.
Conclude
The single counter-example $n=40$ disproves the universal statement, so the claim is false.

Result: The statement is false; $n=40$ gives $1681 = 41^2$ , which is not prime.

Typical mistakes

Reaching for induction on a statement with no integer index, where a direct algebraic proof is intended.
Believing that a convincing inductive step alone secures the result — the base case and the first implication are essential.

Active revision

Decide, with a brief justification, which proof method is most appropriate for each: (a) $n^3 - n$ is divisible by $6$ for all integers $n\geq 1$ ; (b) the statement 'if $n$ is prime then $n$ is odd'; (c) $\sqrt{2}$ is irrational.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

References & sources

Sources

Department for Education

Further mathematics: AS and A level content (GCE subject content)

AQA

AQA A-level Further Mathematics 7367 specification

Proof

Key points

The structure on a first example

Key points

Sum of squares by induction

Key points

Divisibility by 8

Key points

The nth power of a shear matrix

Key points

Choosing a method: disproof by counter-example

Sources