What is not using the inductive hypothesis?

The n = k+1 working must explicitly use the assumed n = k result, otherwise it is not induction.

AQA AQA 2022-style practice: Prove by induction that 7^n - 1 is divisible by 6 for all positive integers n.

Base case: n = 1 gives 7 - 1 = 6, divisible by 6. Assume true for n = k: 7^k - 1 = 6m for some integer m, so 7^k = 6m + 1. Consider n = k+1: 7^k+1 - 1 = 7· 7^k - 1 = 7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 = 6(7m + 1). Since 7m + 1 is an integer, 7^k+1 - 1 is divisible by 6. As the base case holds and P(k) P(k+1), by induction 7^n - 1 is divisible by 6 for all positive integers n. Markers reward the base case, substituting the hypothesis 7^k = 6m + 1, factoring out 6, and the conclusion.

EnglandFurther MathsSyllabus dot point

How does proof by induction work, and how do you use it for sums, divisibility and matrices?

Proof by mathematical induction applied to summation formulae, divisibility results, recurrence relations and powers of matrices, with a clearly stated base case, inductive step and conclusion.

A focused answer to the AQA A-Level Further Mathematics proof by induction content, covering the structure of an induction proof and its use for summation formulae, divisibility results, recurrence relations and powers of matrices, with a clear base case, inductive step and conclusion.

Generated by Claude Opus 4.810 min answerUpdated 2026-06-02

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 structure of an induction proof
Summation formulae
Divisibility, recurrences and matrices

What this dot point is asking

AQA wants you to write rigorous proofs by mathematical induction, with a clearly stated base case, a clearly stated inductive hypothesis and step, and a final conclusion. You must apply it to summation formulae, divisibility statements, recurrence relations and powers of matrices.

The structure of an induction proof

Every proof has the same skeleton: state the proposition, prove the base case, assume the result for $n = k$ , prove it for $n = k+1$ using the assumption, then write the standard conclusion. The logic is a chain of dominoes. The base case knocks over the first domino, and the inductive step guarantees that each domino knocks over the next; together they force every domino to fall. Each part carries marks in its own right, and a frequent examiner complaint is that candidates rush the step or omit the conclusion entirely. Write the inductive hypothesis explicitly as a labelled assumption, manipulate the $n = k+1$ expression so the assumed $n = k$ result can be substituted in, and finish with the formal sentence linking the base case and the implication.

Summation formulae

Prove a summation formula

Prove that $\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$ for all positive integers $n$ .

Step 1: Prove the base case

When $n = 1$ the sum contains only the single term $1$ . The formula gives $\frac{1 \times 2}{2} = 1$ , so both sides agree and $P(1)$ is true.

Step 2: State the inductive hypothesis

Assume $P(k)$ is true for some positive integer $k$ , that is:

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

Step 3: Prove $P(k+1)$

To reach the $(k+1)$ th partial sum, add the next term $(k+1)$ to the assumed sum. We then factor out $(k+1)$ to match the formula's structure:

\sum_{r=1}^{k+1} r = \frac{k(k+1)}{2} + (k+1) = (k+1)\!\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}.

This is precisely the formula with $n = k + 1$ , so $P(k+1)$ is true.

Step 4: State the conclusion

Since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ , by mathematical induction the result holds for all positive integers $n$ .

Divisibility, recurrences and matrices

For a divisibility result, the standard tactic is to write $f(k+1)$ in terms of $f(k)$ , substitute the assumed multiple, and factor the divisor out of the whole expression. For a recurrence relation, you assume the closed form holds for the previous one or two terms and use the recurrence to produce the next. For powers of a matrix $M$ , you prove a claimed formula for $M^n$ by writing $M^{k+1} = M^k M$ , substituting the assumed form of $M^k$ , and multiplying out to show it matches the formula at $n = k+1$ . In every case the inductive step must visibly use the hypothesis, because a step that does not invoke $P(k)$ is not a proof by induction at all.

Prove a divisibility result

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

Step 1: Prove the base case

When $n = 1$ we get $3^2 - 1 = 9 - 1 = 8$ , which is divisible by $8$ , so $P(1)$ is true.

Step 2: State the inductive hypothesis

Assume $P(k)$ : $3^{2k} - 1 = 8m$ for some integer $m$ , so $3^{2k} = 8m + 1$ .

Step 3: Prove the result for $n = k + 1$

We need to show $3^{2(k+1)} - 1$ is divisible by $8$ . We factor $3^{2(k+1)}$ as $9 \cdot 3^{2k}$ and substitute the hypothesis:

3^{2(k+1)} - 1 = 9 \cdot 3^{2k} - 1 = 9(8m + 1) - 1 = 72m + 9 - 1 = 72m + 8 = 8(9m + 1).

Since $9m + 1$ is an integer, $3^{2(k+1)} - 1$ is divisible by $8$ .

Step 4: State the conclusion

Since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ , by induction $3^{2n} - 1$ is divisible by $8$ for all positive integers $n$ .

A matrix example shows the same skeleton in a different setting. To prove $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^{n} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ , the base case at $n = 1$ is immediate. Assuming the form holds for $n = k$ , multiply by the matrix: $\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}$ , which is the formula at $n = k+1$ . The conclusion is then stated in the usual words. Whatever the context, the marks split across a correct base case, an explicit use of the hypothesis in the step, and the formal closing statement, so never omit any of the three.

Exam-style practice questions

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

AQA 20206 marksProve by induction that

\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: when $n = 1$ the sum is $1\times 2 = 2$ and the formula gives $\frac{1}{3}(1)(2)(3) = 2$ , so it holds.

Assume true for $n = k$ : $\sum_{r=1}^{k} r(r+1) = \frac{1}{3}k(k+1)(k+2)$ .

Then $\sum_{r=1}^{k+1} r(r+1) = \frac{1}{3}k(k+1)(k+2) + (k+1)(k+2)$ . Factor 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$ . Since it is true for $n = 1$ , and true for $k$ implies true for $k+1$ , by induction it holds for all positive integers $n$ .

Markers reward the base case, explicit use of the hypothesis, the factorisation, and the formal conclusion.

AQA 20226 marksProve by induction that

7^{n} - 1

is divisible by

6

for all positive integers

n

Show worked answer →

Base case: $n = 1$ gives $7 - 1 = 6$ , divisible by $6$ .

Assume true for $n = k$ : $7^{k} - 1 = 6m$ for some integer $m$ , so $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)$ .

Since $7m + 1$ is an integer, $7^{k+1} - 1$ is divisible by $6$ .

As the base case holds and $P(k) \Rightarrow P(k+1)$ , by induction $7^n - 1$ is divisible by $6$ for all positive integers $n$ .

Markers reward the base case, substituting the hypothesis $7^k = 6m + 1$ , factoring out $6$ , and the conclusion.

Related dot points

Sources & how we know this

AQA A-level Further Mathematics (7367) specification — AQA (2017)