What is not using the assumption?

The inductive step must visibly use the n = k case; if your k + 1 working never refers to the hypothesis, you have not done induction.

What is a vague conclusion?

Marks are awarded for the closing sentence. Write "true for n = 1, and if true for n = k then true for n = k + 1, hence true for all positive integers n by induction."

CCEA CCEA AS 2021-style practice: Prove by induction that _r=1^n r(r + 1) = (1)/(3)n(n + 1)(n + 2) for all positive integers n.

Base case n = 1: the left-hand side is 1(2) = 2, and the right-hand side is (1)/(3)(1)(2)(3) = 2. They agree, so the result holds for n = 1. Inductive step: assume it holds for n = k, that is _r=1^k r(r + 1) = (1)/(3)k(k + 1)(k + 2). Add the next term (k + 1)(k + 2): _r=1^k+1 r(r + 1) = (1)/(3)k(k + 1)(k + 2) + (k + 1)(k + 2). Take out (k + 1)(k + 2): = (k + 1)(k + 2)((k)/(3) + 1) = (k + 1)(k + 2)·(k + 3)/(3) = (1)/(3)(k + 1)(k + 2)(k + 3). This is the formula with n = k + 1. Conclusion: true for n = 1 and, if true for n = k, then true for n = k + 1, so by induction it holds for all positive integers n. Markers reward the base case, the assumption, the algebra reaching the k + 1 form, and a clear conclusion.

Northern IrelandFurther MathsSyllabus dot point

How does proof by mathematical induction establish a result for all positive integers?

The principle of mathematical induction and its use to prove results about summation of series, divisibility and other statements indexed by the positive integers.

A CCEA AS Further Maths answer on the principle of mathematical induction, the base case, inductive step and conclusion, and applying induction to prove summation formulae and divisibility results for all positive integers.

Generated by Claude Opus 4.812 min answerUpdated 2026-06-16

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

CCEA wants you to state and apply the principle of mathematical induction: prove a result is true for a starting value (the base case), assume it for $n = k$ and deduce it for $n = k + 1$ (the inductive step), then conclude it holds for all positive integers. The two staple contexts are summation formulae and divisibility statements; the marks are as much for the structure and wording as for the algebra.

The answer

The principle of induction

The idea is a chain of dominoes: the base case knocks over the first, and the inductive step guarantees each domino topples the next.

Series proofs

Divisibility proofs

A divisibility proof

Prove by induction that $5^n + 2 \cdot 11^n$ is divisible by $3$ for all positive integers $n$ .

step Base case

For $n = 1$ : $5 + 2(11) = 5 + 22 = 27 = 3 \times 9$ , divisible by $3$ . The statement holds for $n = 1$ .

step Inductive hypothesis

Assume $5^k + 2\cdot 11^k = 3m$ for some integer $m$ .

step Inductive step

Consider $n = k + 1$ :

5^{k+1} + 2\cdot 11^{k+1} = 5\cdot 5^k + 22\cdot 11^k.

Write

22 = 5 + 17

so that part matches the assumption:

= 5\big(5^k + 2\cdot 11^k\big) + 17\cdot 11^k - 10\cdot 11^k = 5(3m) + (22 - 10)\cdot 11^k.

More directly:

5\cdot 5^k + 22\cdot 11^k = 5(5^k + 2\cdot 11^k) + 12\cdot 11^k = 5(3m) + 12\cdot 11^k = 3\big(5m + 4\cdot 11^k\big)

, a multiple of

3

step Conclusion

True for $n = 1$ , and truth for $k$ implies truth for $k + 1$ , so by induction $5^n + 2\cdot 11^n$ is divisible by $3$ for all positive integers $n$ .

Examples in context

Example 1. Verifying a conjectured formula. A student notices that the sums $1, 1 + 3, 1 + 3 + 5, \dots$ give the squares $1, 4, 9, \dots$ and conjectures $\sum_{r=1}^{n}(2r - 1) = n^2$ . Induction turns the pattern from "looks true" into a proof valid for every $n$ .

Example 2. Recurrence in algorithms. Computer scientists prove that a recursive routine is correct, or runs in a stated number of steps, by induction on the input size: it works for the smallest input, and each call reduces to a smaller one that is assumed correct. The same base-case-and-step structure underpins both maths and computing proofs.

Try this

Q1. State the three parts of a proof by induction. [2 marks]

Cue. Base case, inductive step (assume $k$ , prove $k+1$ ), and conclusion for all $n$ .

Q2. In proving a sum formula, what do you add to the assumed sum in the inductive step? [1 mark]

Cue. The $(k + 1)$ th term, $f(k + 1)$ .

Q3. To prove $4^n - 1$ is divisible by $3$ , what is the base case value at $n = 1$ ? [1 mark]

Cue. $4^1 - 1 = 3$ , divisible by $3$ .

Exam-style practice questions

Practice questions written in the style of CCEA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

CCEA AS 20216 marksProve by induction that

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

for all positive integers

n

Show worked answer →

Base case $n = 1$ : the left-hand side is $1(2) = 2$ , and the right-hand side is $\frac{1}{3}(1)(2)(3) = 2$ . They agree, so the result holds for $n = 1$ .

Inductive step: assume it holds for $n = k$ , that is $\sum_{r=1}^{k} r(r + 1) = \frac{1}{3}k(k + 1)(k + 2)$ . Add the next term $(k + 1)(k + 2)$ :

$\sum_{r=1}^{k+1} r(r + 1) = \frac{1}{3}k(k + 1)(k + 2) + (k + 1)(k + 2).$

Take out $(k + 1)(k + 2)$ :

$= (k + 1)(k + 2)\left(\frac{k}{3} + 1\right) = (k + 1)(k + 2)\cdot\frac{k + 3}{3} = \frac{1}{3}(k + 1)(k + 2)(k + 3).$

This is the formula with $n = k + 1$ . Conclusion: true for $n = 1$ and, if true for $n = k$ , then true for $n = k + 1$ , so by induction it holds for all positive integers $n$ . Markers reward the base case, the assumption, the algebra reaching the $k + 1$ form, and a clear conclusion.

CCEA AS 20196 marksProve by induction that

7^n - 1

is divisible by

6

for all positive integers

n

Show worked answer →

Base case $n = 1$ : $7^1 - 1 = 6$ , which is divisible by $6$ , so the statement holds for $n = 1$ .

Inductive step: assume $7^k - 1$ is divisible by $6$ , so $7^k - 1 = 6m$ for some integer $m$ , giving $7^k = 6m + 1$ . Consider $n = k + 1$ :

$7^{k+1} - 1 = 7\cdot 7^k - 1 = 7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 = 6(7m + 1).$

This is a multiple of $6$ , so the statement holds for $n = k + 1$ .

Conclusion: true for $n = 1$ , and truth for $n = k$ implies truth for $n = k + 1$ , so by induction $7^n - 1$ is divisible by $6$ for all positive integers $n$ . Markers reward the base case, using the assumption to substitute $7^k = 6m + 1$ , factoring out $6$ , and the conclusion.

Related dot points

Sources & how we know this

CCEA GCE Further Mathematics specification — CCEA (2018)