Paper 1 · Further Pure 1 ✦

Proof by Induction

Knock over the first domino, and prove each one topples the next. The maths is usually easy; the marks are in saying it in exactly the right words.

Syllabus 1.7Series · divisibility · Aⁿ · sequencesStructure = marks

What the examiner expects you to do

Use mathematical induction to establish a given result — for series, divisibility, matrix powers $𝐀^{n}$ , sequences and $n$ th derivatives.
Recognise when conjecture from a limited trial, followed by inductive proof, is a useful strategy, and carry it out in simple cases.

§1 The method — and the exact words

Induction has four parts. Every one carries marks, and the last one is the part most candidates omit.

◆ The skeleton — write this every single time

1 · Define the statement

Let

P (n)

be the statement [write the result out in full, with $n$ in it].

2 · Base case

When

n = 1

: LHS

= \dots

, RHS

= \dots

. These are equal, so

P (1)

is true.

3 · Inductive step

Assume

P (k)

is true for some positive integer

k

, i.e. [write the assumption out]. Then consider the

n = k + 1

case … and use the assumption … which is

P (k + 1)

. So

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

4 · Conclusion

Since

P (1)

is true and

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

, by mathematical induction

P (n)

is true for all positive integers

n

★ A* tip — the two habits that separate full marks from most

Write down what you are aiming at before you start the algebra. If you know $P (k + 1)$ should read $\frac{1}{4} (k + 1)^{2} (k + 2)^{2}$ , you know exactly which factorised form to steer towards.
Point at the moment you use the assumption. A proof that never visibly uses $P (k)$ is not an inductive proof, and examiners look for that line specifically.

⚠ "Assume it is true for all

k

" is wrong

You assume it for some particular $k$ — one domino — and deduce the next. Assuming it for all $n$ assumes what you are proving. Say "assume $P (k)$ is true for some positive integer $k$ ".

§2 Series

✎ Worked example — prove

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

Statement. Let $P (n)$ be $\sum_{r = 1}^{n} r^{3} = \frac{1}{4} n^{2} (n + 1)^{2}$ .

Base case. When $n = 1$ : LHS $= 1^{3} = 1$ ; RHS $= \frac{1}{4} (1)^{2} (2)^{2} = 1$ . Equal, so $P (1)$ is true.

Inductive step. Assume $P (k)$ : $\sum_{r = 1}^{k} r^{3} = \frac{1}{4} k^{2} (k + 1)^{2}$ . Then

\sum_{r = 1}^{k + 1} r^{3} = \underset{use the assumption}{\underset{⏟}{\sum_{r = 1}^{k} r^{3}}} + (k + 1)^{3} = \frac{1}{4} k^{2} (k + 1)^{2} + (k + 1)^{3} .

Take out $\frac{1}{4} (k + 1)^{2}$ — aiming at the target form:

= \frac{1}{4} (k + 1)^{2} [k^{2} + 4 (k + 1)] = \frac{1}{4} (k + 1)^{2} (k^{2} + 4 k + 4) = \frac{1}{4} (k + 1)^{2} (k + 2)^{2},

which is exactly $P (k + 1)$ (replace $n$ by $k + 1$ in the statement). So $P (k) \Rightarrow P (k + 1)$ .

Conclusion. $P (1)$ is true and $P (k) \Rightarrow P (k + 1)$ , so by induction $P (n)$ is true for all positive integers $n$ . $■$

★ The move that makes series inductions easy

Always split off the last term: $\sum_{r = 1}^{k + 1} = \sum_{r = 1}^{k} + (k + 1) th term$ . Then factor out the common bracket from the target and match what is left.

§3 Divisibility

◆ The technique

To show $f (n)$ is divisible by $m$ , express $f (k + 1)$ in terms of $f (k)$ :

f (k + 1) = λ f (k) + m \times (an integer) .

Then if $m | f (k)$ , both pieces are divisible by $m$ , so $m | f (k + 1)$ . Finding the right $λ$ is the whole skill: it is usually the base of the fastest-growing exponential.

✎ Worked example —

3^{2 n} + 2 \times 5^{n} - 3

is divisible by 8

Statement. Let $P (n)$ be " $f (n) = 3^{2 n} + 2 \times 5^{n} - 3$ is divisible by $8$ ".

Base case. $f (1) = 9 + 10 - 3 = 16 = 8 \times 2$ , so $P (1)$ is true.

Inductive step. Assume $f (k) = 3^{2 k} + 2 \times 5^{k} - 3$ is divisible by $8$ . Now

f (k + 1) = 3^{2 k + 2} + 2 \times 5^{k + 1} - 3 = 9 \times 3^{2 k} + 10 \times 5^{k} - 3 .

The fastest-growing term has base $9$ , so subtract $9 f (k)$ :

f (k + 1) - 9 f (k) = (10 \times 5^{k} - 18 \times 5^{k}) + (- 3 + 27) = - 8 \times 5^{k} + 24,

⟹ f (k + 1) = 9 f (k) + 8 (3 - 5^{k}) .

$9 f (k)$ is divisible by $8$ by the assumption, and $8 (3 - 5^{k})$ is a multiple of $8$ because $3 - 5^{k}$ is an integer. So $f (k + 1)$ is divisible by $8$ , i.e. $P (k) \Rightarrow P (k + 1)$ .

Conclusion. By induction, $3^{2 n} + 2 \times 5^{n} - 3$ is divisible by $8$ for all positive integers $n$ . $■$

Check: $f (2) = 81 + 50 - 3 = 128$ , and $9 f (1) + 8 (3 - 5) = 144 - 16 = 128$ ✓

⚠ "Is a multiple of 8" needs an integer

Writing $f (k) = 8 M$ with " $M$ an integer" at the start makes the last line airtight: you can then say $f (k + 1) = 8 (9 M + 3 - 5^{k})$ , and the bracket is visibly an integer. Vague phrasing like "so it works" scores nothing.

§4 Powers of a matrix

✎ Worked example — a given

𝐀^{n}

Prove that for $𝐀 = (\begin{array}{cc} 4 & - 1 \\ 6 & - 1 \end{array})$ ,

𝐀^{n} = (\begin{array}{cc} 3 \cdot 2^{n} - 2 & 1 - 2^{n} \\ 6 \cdot 2^{n} - 6 & 3 - 2^{n + 1} \end{array}) .

Base case. $n = 1$ gives $(\begin{array}{cc} 6 - 2 & 1 - 2 \\ 12 - 6 & 3 - 4 \end{array}) = (\begin{array}{cc} 4 & - 1 \\ 6 & - 1 \end{array}) = 𝐀$ ✓

Inductive step. Assume the formula holds for $n = k$ . Then $𝐀^{k + 1} = 𝐀^{k} 𝐀$ :

(\begin{array}{cc} 3 \cdot 2^{k} - 2 & 1 - 2^{k} \\ 6 \cdot 2^{k} - 6 & 3 - 2^{k + 1} \end{array}) (\begin{array}{cc} 4 & - 1 \\ 6 & - 1 \end{array}) .

Top-left: $4 (3 \cdot 2^{k} - 2) + 6 (1 - 2^{k}) = 12 \cdot 2^{k} - 8 + 6 - 6 \cdot 2^{k} = 6 \cdot 2^{k} - 2 = 3 \cdot 2^{k + 1} - 2$ ✓

Top-right: $- (3 \cdot 2^{k} - 2) - (1 - 2^{k}) = - 3 \cdot 2^{k} + 2 - 1 + 2^{k} = 1 - 2 \cdot 2^{k} = 1 - 2^{k + 1}$ ✓

Bottom-left: $4 (6 \cdot 2^{k} - 6) + 6 (3 - 2^{k + 1}) = 24 \cdot 2^{k} - 24 + 18 - 12 \cdot 2^{k} = 12 \cdot 2^{k} - 6 = 6 \cdot 2^{k + 1} - 6$ ✓

Bottom-right: $- (6 \cdot 2^{k} - 6) - (3 - 2^{k + 1}) = - 6 \cdot 2^{k} + 6 - 3 + 2 \cdot 2^{k} = 3 - 4 \cdot 2^{k} = 3 - 2^{k + 2}$ ✓

Every entry is the formula with $k + 1$ in place of $k$ , so $P (k) \Rightarrow P (k + 1)$ , and the result follows by induction. $■$

★ A* tip — multiply on the correct side, and convert bases early

Use $𝐀^{k + 1} = 𝐀^{k} 𝐀$ so the assumption is available immediately. And turn every $2 \cdot 2^{k}$ into $2^{k + 1}$ as you go: the target form is what you are matching, and leaving mixed notation is how sign and index errors hide.

§5 Sequences and $n$ th derivatives

✎ Worked example — a recurrence relation

The sequence is defined by $u_{n + 1} = 3 u_{n} - 1$ with $u_{1} = 1$ . Prove that $u_{n} = \frac{1}{2} (1 + 3^{n - 1})$ .

Base case. $u_{1} = \frac{1}{2} (1 + 3^{0}) = \frac{1}{2} (2) = 1$ ✓ matching the given first term.

Inductive step. Assume $u_{k} = \frac{1}{2} (1 + 3^{k - 1})$ . Then, using the recurrence,

u_{k + 1} = 3 u_{k} - 1 = 3 \cdot \frac{1}{2} (1 + 3^{k - 1}) - 1 = \frac{3}{2} + \frac{3}{2} \cdot 3^{k - 1} - 1 = \frac{1}{2} + \frac{1}{2} \cdot 3^{k} = \frac{1}{2} (1 + 3^{k}),

which is the formula with $k + 1$ in place of $k$ (since $(k + 1) - 1 = k$ ). So $P (k) \Rightarrow P (k + 1)$ , and the result follows by induction. $■$

Check: $u_{2} = 3 (1) - 1 = 2$ and $\frac{1}{2} (1 + 3) = 2$ ✓; $u_{3} = 3 (2) - 1 = 5$ and $\frac{1}{2} (1 + 9) = 5$ ✓

✎ Worked example — an

n

th derivative

Prove that $\frac{d^{n}}{d x^{n}} (x e^{x}) = (x + n) e^{x}$ .

Base case. $n = 1$ : by the product rule $\frac{d}{d x} (x e^{x}) = e^{x} + x e^{x} = (x + 1) e^{x}$ ✓

Inductive step. Assume the $k$ th derivative is $(x + k) e^{x}$ . Differentiating once more,

\frac{d^{k + 1}}{d x^{k + 1}} (x e^{x}) = \frac{d}{d x} [(x + k) e^{x}] = e^{x} + (x + k) e^{x} = (x + (k + 1)) e^{x},

which is the formula with $k + 1$ in place of $k$ . By induction the result holds for all positive integers $n$ . $■$

§6 Conjecture first, then prove

The syllabus asks you to spot when a short trial suggests a pattern, and then nail it down with induction. Trial alone is never a proof — but it is how you find the thing to prove.

✎ Worked example —

\sum_{r = 1}^{n} r \times r!

Trial. Compute the first few and look for a pattern next to the factorials:

$n$	1	2	3	4
sum	$1$	$5$	$23$	$119$
compare	$2! - 1$	$3! - 1$	$4! - 1$	$5! - 1$

Conjecture. $\sum_{r = 1}^{n} r \times r! = (n + 1)! - 1$ .

Proof. Base case $n = 1$ : LHS $= 1 \times 1! = 1$ ; RHS $= 2! - 1 = 1$ ✓. Assume it holds for $n = k$ . Then

\sum_{r = 1}^{k + 1} r \times r! = [(k + 1)! - 1] + (k + 1) \times (k + 1)!,

and taking out the common factor $(k + 1)!$ :

= (k + 1)! [1 + (k + 1)] - 1 = (k + 1)! (k + 2) - 1 = (k + 2)! - 1,

which is the conjecture with $k + 1$ in place of $n$ . So by induction it holds for all positive integers $n$ . $■$

⚠ A pattern that holds for

n = 1, \dots, 40

can still be false

Checking cases builds a conjecture, never a proof. Write "this suggests…" for the trial and keep the word "hence" or "therefore" for the induction. Marks are given for knowing the difference.

§7 Interactive: the domino chain

Pick a result and raise $n$ . Each domino is checked independently — the left-hand side is computed from scratch and compared with the formula — so a green chain is real evidence, not a restatement. The base case is starred; the arrows are what the inductive step buys you.

Check up to

n

every domino falls ✎

§8 Examiner traps & A* checklist

⚠ The seven most common mark-losers

No concluding statement. "Hence by induction the result is true for all positive integers $n$ " is a mark on its own, and it is the most frequently dropped one in the whole paper.
Assuming the result "for all $k$ " rather than "for some positive integer $k$ ".
Never visibly using the assumption — the proof then proves nothing.
Stopping at an unfactorised mess instead of steering to the target form with $k + 1$ substituted.
Starting at the wrong base. If the claim is for $n \geq 0$ or $n \geq 2$ , check that value, not $n = 1$ .
In divisibility, saying "is a multiple of $m$ " without producing an explicit integer factor.
In matrix proofs, writing $𝐀^{k + 1} = 𝐀 𝐀^{k}$ and then multiplying in the wrong order — the entries will not match.

★ Before you turn the page

Have I written $P (k + 1)$ out explicitly, so I know what I am steering towards?
Did I check the base case with actual numbers on both sides?
Is my final sentence there, in full?

§9 Video explainers (curated)

▶Induction for series
Curated search — the structure and the standard sum proofs.↗ ▶Induction for divisibility
Curated search — expressing f(k+1) in terms of f(k).↗ ▶Induction for matrix powers
Curated search — proving a given formula for Aⁿ.↗

§10 Check yourself

Score 0 / 5

Q1 · the base case

To prove $\sum_{r = 1}^{n} r^{3} = \frac{1}{4} n^{2} (n + 1)^{2}$ by induction, the base case $n = 1$ requires you to show that:

Solution

LHS $= 1^{3} = 1$ and RHS $= \frac{1}{4} (1)^{2} (1 + 1)^{2} = \frac{1}{4} \times 4 = 1$ . Both are $1$ , so $P (1)$ is true. The trap answer $\frac{1}{4}$ comes from forgetting to square the $(n + 1)$ .

Q2 · divisibility technique

Let $f (n) = 3^{2 n} + 2 \times 5^{n} - 3$ . Which identity makes the inductive step work?

Solution

$f (k + 1) = 9 \times 3^{2 k} + 10 \times 5^{k} - 3$ . Subtracting $9 f (k) = 9 \times 3^{2 k} + 18 \times 5^{k} - 27$ leaves $- 8 \times 5^{k} + 24 = 8 (3 - 5^{k})$ . Both terms on the right are then divisible by $8$ . Check with $k = 1$ : $f (1) = 16, f (2) = 128$ , and $9 (16) + 8 (3 - 5) = 144 - 16 = 128$ ✓

Q3 · conjecture

$\sum_{r = 1}^{n} r \times r!$ equals:

Solution

The first few sums are $1,5,23,119$ , which are $2! - 1, 3! - 1, 4! - 1, 5! - 1$ . So the conjecture is $(n + 1)! - 1$ , proved by induction in §6.

Q4 · sequences

For $u_{n + 1} = 3 u_{n} - 1$ with $u_{1} = 1$ , the closed form is:

Solution

The terms are $1,2,5,14,41, \dots$ . Testing $n = 1$ kills three of the options at once: $\frac{1}{2} (1 + 3^{0}) = 1$ ✓, while $\frac{1}{2} (1 + 3) = 2$ , $3^{0} = 1$ (but then $n = 2$ gives $3 \neq 2$ ), and $\frac{1}{2} (3^{0} - 1) = 0$ . The proof is in §5.

Q5 · full method — try it on paper first

Prove by induction that, for all positive integers $n$ ,

{(\begin{array}{cc} 1 & 1 \\ 0 & 2 \end{array})}^{n} = (\begin{array}{cc} 1 & 2^{n} - 1 \\ 0 & 2^{n} \end{array}) .

Solution

Statement. Let $P (n)$ be $𝐀^{n} = (\begin{array}{cc} 1 & 2^{n} - 1 \\ 0 & 2^{n} \end{array})$ , where $𝐀 = (\begin{array}{cc} 1 & 1 \\ 0 & 2 \end{array})$ .

Base case. When $n = 1$ the formula gives $(\begin{array}{cc} 1 & 2^{1} - 1 \\ 0 & 2^{1} \end{array}) = (\begin{array}{cc} 1 & 1 \\ 0 & 2 \end{array}) = 𝐀$ . So $P (1)$ is true.

Inductive step. Assume $P (k)$ for some positive integer $k$ , i.e. $𝐀^{k} = (\begin{array}{cc} 1 & 2^{k} - 1 \\ 0 & 2^{k} \end{array})$ . Then, multiplying on the right by $𝐀$ so the assumption can be used directly,

𝐀^{k + 1} = 𝐀^{k} 𝐀 = (\begin{array}{cc} 1 & 2^{k} - 1 \\ 0 & 2^{k} \end{array}) (\begin{array}{cc} 1 & 1 \\ 0 & 2 \end{array}) = (\begin{array}{cc} 1 & 1 + 2 (2^{k} - 1) \\ 0 & 2 \cdot 2^{k} \end{array}) .

Simplify the top-right entry: $1 + 2 \cdot 2^{k} - 2 = 2^{k + 1} - 1$ ; and the bottom-right is $2^{k + 1}$ . Hence

𝐀^{k + 1} = (\begin{array}{cc} 1 & 2^{k + 1} - 1 \\ 0 & 2^{k + 1} \end{array}),

which is precisely $P (k + 1)$ . So $P (k) \Rightarrow P (k + 1)$ .

Conclusion. $P (1)$ is true, and $P (k) \Rightarrow P (k + 1)$ for every positive integer $k$ . Therefore, by mathematical induction, $P (n)$ is true for all positive integers $n$ . $■$

Check with $n = 3$ : $𝐀^{3} = (\begin{array}{cc} 1 & 3 \\ 0 & 4 \end{array}) (\begin{array}{cc} 1 & 1 \\ 0 & 2 \end{array}) = (\begin{array}{cc} 1 & 7 \\ 0 & 8 \end{array})$ , and the formula gives $(\begin{array}{cc} 1 & 2^{3} - 1 \\ 0 & 2^{3} \end{array}) = (\begin{array}{cc} 1 & 7 \\ 0 & 8 \end{array})$ ✓

FP1 · Topic 7 · Proof by Induction

Proof by Induction

What the examiner expects you to do

§1 The method — and the exact words

§2 Series

§3 Divisibility

§4 Powers of a matrix

§5 Sequences and nth derivatives

§6 Conjecture first, then prove

§7 Interactive: the domino chain

§8 Examiner traps & A* checklist

§9 Video explainers (curated)

§10 Check yourself

§5 Sequences and $n$ th derivatives