Proof by induction

Further Maths · Further Pure Mathematics 1. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Further Maths topics

The idea

Induction proves that a statement is true for every positive integer n. Think of a row of dominoes: if the first one falls, and each one knocks over the next, then they all fall.

So a proof has two parts. The base case checks the statement for the first value, usually n = 1. The inductive step assumes the statement is true for n = k and uses that assumption to show it is true for n = k + 1. A final sentence joins the two parts.

Sometimes no formula is given. Then work out the first few cases, spot the pattern, write it as a conjecture and prove it by induction. A pattern alone is not a proof.

Rules to remember

Four parts: (1) show true for n = 1; (2) assume true for n = k; (3) show true for n = k + 1 using the assumption; (4) write the conclusion
Sums: (sum to k + 1 terms) = (assumed sum to k terms) + (the (k + 1)th term), then factorise to the required form
Divisibility: write f(k + 1) in terms of f(k), or show that f(k + 1) − m × f(k) is a multiple of the divisor for a suitable number m
Matrix powers: M^k+1 = M^k × M, with the assumed form put in for M^k
Sequences: put the assumed formula for u_k into the recurrence relation to get u_k+1
If the result starts at n = N, the base case is n = N, not n = 1
Conjecture questions: calculate cases n = 1, 2, 3, guess the formula, then prove it

Common mistake

Students leave out the base case or never use the assumption for n = k. Without the base case nothing has been proved, and the step for k + 1 must clearly use the assumed result.

Worked example

Prove by induction that f(n) = 5ⁿ + 3 is divisible by 4 for every positive integer n.

Base case: f(1) = 5 + 3 = 8 = 4 × 2, so the statement is true for n = 1.
Assume f(k) = 5^k + 3 is divisible by 4.
f(k + 1) = 5 × 5^k + 3 = 5(5^k + 3) − 15 + 3 = 5f(k) − 12. Both 5f(k) and 12 are multiples of 4, so f(k + 1) is divisible by 4.
True for n = 1, and true for n = k implies true for n = k + 1, so it is true for all positive integers n.

Answer: f(k + 1) = 5f(k) − 12, so 5ⁿ + 3 is divisible by 4 for all positive integers n.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Read the full notes

Proof by Induction

Keep going

← Vectors Hyperbolic functions →Take a Further Maths test