Proof by induction (divisibility)

Proof by induction

A-level Further Maths (9FM0) · Core Pure

ORIGINAL

Basis, assumption, inductive step via f(k+1) − f(k), and the full conclusion the mark scheme insists on.

Board and spec code confirmed against Edexcel 9FM0 · registry checked 2026-07-17How this checking works

Question

Prove by induction that, for all

n \in \mathbb{Z}^+

f(n) = 5^n + 8n + 3

is divisible by 4.

Every step worked, with the reasoning.

1
$n = 1$ : $f(1) = 5 + 8 + 3 = 16 = 4 \times 4$ , so the result is true for $n = 1$ .
Basis step: show the statement holds for the first value.
2
Assume the result is true for $n = k$ , i.e. $f(k) = 5^k + 8k + 3$ is divisible by 4.
The inductive hypothesis — state it explicitly.
3
$f(k+1) - f(k) = 5^{k+1} + 8(k+1) + 3 - (5^k + 8k + 3) = 5 \cdot 5^k - 5^k + 8 = 4(5^k + 2)$
Write $5^{k+1}$ as $5 \cdot 5^k$ ; the $8k$ and $3$ cancel, leaving $4 \cdot 5^k + 8$ .
4
$f(k+1) = f(k) + 4(5^k + 2)$
$f(k)$ is divisible by 4 by the assumption and $4(5^k + 2)$ is a multiple of 4, so $f(k+1)$ is divisible by 4.
5
If the result is true for $n = k$ , then it is true for $n = k + 1$ . As it is true for $n = 1$ , it is true for all $n \in \mathbb{Z}^+$ .
The conclusion must link all of it: true for $n = k$ implies true for $n = k + 1$ , true for $n = 1$ , so true for all positive integers.

Answer: $5^n + 8n + 3$ is divisible by 4 for all $n \in \mathbb{Z}^+$ .