# Proof by induction

> CIE A-Level Further Mathematics · 9231 Further Pure 1
> Source: https://www.owlsprep.com/study/cie-9231-u1-proof-by-induction/

This module covers the formal 4-step structure of mathematical induction, plus its application to summation, divisibility and matrix power proofs tailored for CIE 9231 Further Pure 1 exams.

**Prerequisites:** [Basic algebraic manipulation and polynomial expansion](https://www.owlsprep.com/study/cie-9231-u1-algebra-manipulation/); [2x2 matrix multiplication rules](https://www.owlsprep.com/study/cie-9231-u1-matrix-basics/)

## Learning objectives

- Recall the 4 standard formal steps of mathematical induction for positive integers
- Apply induction to prove summation, divisibility, and 2x2 matrix power identity statements
- Identify and fix common logical gaps that cause lost marks in exam responses
- Structure full induction proofs to meet CIE 9231 mark scheme requirements

## Core Formal Structure of Induction

**Principle of Mathematical Induction** — If a statement P(n) is true for n=1, and the truth of P(k) implies the truth of P(k+1) for all positive integers k, then P(n) is true for all n ∈ ℕ

> **tip**
>
> CIE examiners explicitly award 1 standalone mark for a clear final conclusion referencing the induction principle, never skip this step even if you are running out of time.

**Worked example:** Prove that the sum of the first n positive integers equals n(n+1)/2 using induction

1. Step 1: Base Case. Test n=1: LHS = 1, RHS = 1(2)/2 = 1. P(1) is true.
2. Step 2: Inductive Hypothesis. Assume P(k) is true: $\sum_{r=1}^k r = \frac{k(k+1)}{2}$
3. Step 3: Inductive Step. Add (k+1) to both sides: $\sum_{r=1}^{k+1} r = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$, which matches P(k+1)
4. Step 4: Conclusion. Since P(1) is true, and P(k) true implies P(k+1) true, P(n) holds for all positive integers n.

**Check your understanding**

Test your understanding of mark weight for induction steps

1. Which step of a standard induction proof is worth the largest share of marks in a typical 9231 question?

   - Base case
   - Inductive hypothesis
   - Inductive step
   - Final conclusion

   *Why:* The algebraic manipulation in the inductive step is usually worth 4-6 of the total 8-10 marks for a full induction question.

## Induction for Summation Identities

Summation proofs are the most frequently asked induction type in CIE 9231 Paper 1. The key rule is to isolate the (k+1)th term from the sum when moving from P(k) to P(k+1), then rearrange to match the required closed form.

$$\sum_{r=1}^{k+1} f(r) = \sum_{r=1}^{k} f(r) + f(k+1)$$

**Worked example:** Prove that $\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}$ for all positive integers n

1. Base case n=1: LHS = 1, RHS = 1*2*3/6 = 1, so P(1) holds.
2. Inductive hypothesis: Assume $\sum_{r=1}^k r^2 = \frac{k(k+1)(2k+1)}{2}$
3. Inductive step: Add $(k+1)^2$ to both sides:
4. $$\sum_{r=1}^{k+1} r^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$$
5. $$= \frac{(k+1)}{6} \left[ 2k^2 +k + 6k +6 \right] = \frac{(k+1)(k+2)(2k+3)}{6}$$
6. This matches the required form for n=k+1, so P(k) → P(k+1), followed by the standard universal conclusion.

> **Exam tip:** Always expand the target RHS for n=k+1 first, then work backwards from the LHS to match it, to avoid getting stuck on messy algebra.

## Induction for Divisibility Proofs

Divisibility proofs require you to show a given expression f(n) is exactly divisible by a fixed integer d for all positive n. The standard technique rewrites f(k+1) in terms of f(k) plus a multiple of d.

**Divisibility Notation** — The integer d divides f(n) exactly, with no remainder, so f(n) = d * m for some integer m.

*Notation:* $d \mid f(n)$

> **mnemonic**
>
> For divisibility proofs, use the 'subtract and add the base' trick: $f(k+1) = a f(k) + (a-1)c$, where a is the base of the exponential term, to factor out d immediately.

**Worked example:** Prove that $7^n - 1$ is divisible by 6 for all positive integers n

1. Base case n=1: $7^1 -1 = 6$, which is divisible by 6, so P(1) is true.
2. Inductive hypothesis: Assume $7^k -1 = 6m$ for some integer m.
3. Inductive step: Rewrite $7^{k+1} -1 = 7 \times 7^k -1$
4. $$= 7 \times (6m +1) -1 = 42m + 6 = 6(7m +1)$$
5. This is a clear multiple of 6, so P(k+1) holds, followed by the standard conclusion.

## Induction for Matrix Power Identities

Matrix induction proofs require you to prove that raising a given 2x2 or 3x3 matrix M to the power n produces a specified standard form matrix. The inductive step uses the identity $M^{k+1} = M^k \times M$.

**Worked example:** Prove that for $M = \begin{pmatrix}1 & 2 \\ 0 & 1\end{pmatrix}$, $M^n = \begin{pmatrix}1 & 2n \\ 0 & 1\end{pmatrix}$ for all positive integers n

1. Base case n=1: $M^1 = M$, which matches the RHS with 2*1=2, so P(1) is true.
2. Inductive hypothesis: Assume $M^k = \begin{pmatrix}1 & 2k \\ 0 & 1\end{pmatrix}$
3. $$M^{k+1} = M^k M = \begin{pmatrix} 1 & 2k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$$
4. $$= \begin{pmatrix} 1 & 2(k+1) \\ 0 & 1 \end{pmatrix}$$
5. This matches the required form for n=k+1, so P(k) → P(k+1), followed by the standard conclusion.

**Exam command terms**

CIE uses these standard command terms for induction questions with specific mark requirements:

- **Prove by induction** — You must show all 4 steps explicitly, no shortcuts allowed

- **Show that** — You may skip the formal conclusion only if the question already specifies to use induction

## Common pitfalls

- **Wrong:** Skipping the base case entirely to go straight to the inductive step
  - Why it fails: This creates a logical fallacy where you can prove false statements like 'all integers are equal', and you lose 2-3 easy marks
  - Correct: Always test n=1 (or the specified starting value) first, and state the result clearly.
- **Wrong:** Writing 'assume P(n) is true' instead of 'assume P(k) is true'
  - Why it fails: This confuses the general variable with the specific fixed integer k used in the hypothesis, losing a communication mark
  - Correct: Explicitly define k as a positive integer for which P(k) is assumed true.
- **Wrong:** Failing to explicitly state the final conclusion linking back to the induction principle
  - Why it fails: CIE mark schemes allocate a standalone 1 mark for this concluding statement, which is often missed by rushed students
  - Correct: End every proof with the standard line: 'Since P(1) is true, and P(k) true implies P(k+1) true, P(n) holds for all positive integers n'.
- **Wrong:** In divisibility proofs, not defining the integer multiple (e.g. not stating $7^k -1 = 6m$ where m is an integer)
  - Why it fails: Examiners will deduct marks for not justifying that the resulting expression is a whole multiple of d
  - Correct: Explicitly name the integer multiple variable and state it is an integer.
- **Wrong:** In matrix induction, multiplying $M \times M^k$ instead of $M^k \times M$
  - Why it fails: Matrix multiplication is not commutative, so this will produce an incorrect result for non-commuting matrices
  - Correct: Always write $M^{k+1} = M^k \times M$ to match the inductive hypothesis structure.

## Cheatsheet

| Proof Type | Key Inductive Step Identity | Typical Mark Weight |
| --- | --- | --- |
| Summation | $\sum_{r=1}^{k+1} f(r) = \sum_{r=1}^k f(r) + f(k+1)$ | 6-7 marks |
| Divisibility | $f(k+1) = a f(k) + c d$ | 5-6 marks |
| Matrix Power | $M^{k+1} = M^k M$ | 7-8 marks |
| Recurrence Relation | $u_{k+1} = f(u_k)$ | 6-7 marks |

## What's next

You have now mastered the core structure and 3 most common induction proof types that appear in CIE 9231 Further Pure 1 exams. To reinforce your skills, practice full past-style induction questions that combine multiple concepts, including inequalities and recurrence relation proofs, which are the next level of difficulty for this topic. You can also review related proof methods including proof by contradiction, another frequently tested topic in Further Pure 1, to build a full toolkit of formal proof techniques for your exam. Mastering induction will also support you when you work on sequences and series proofs later in the syllabus.

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9231-u1-proof-by-induction/