A LevelFurther MathsEdexcelCore PureRevision NotesProofProof by InductionCommon Cases of Proof by Induction

Common Cases of Proof by Induction (Edexcel A Level Further Maths: Core Pure): Revision Note

Exam code: 9FM0

Written by: Dan Finlay

Reviewed by: Lucy Kirkham

Updated on 2 July 2026

Proof by induction - sequences

What are the steps for proof by induction with sequences?

STEP 1: The basic step
- Show the result is true for the base case
  - If the recursive relation formula for the next term involves the previous two terms then you need to show the position-to-term formula works the first two given terms which will be given as part of the definition of the sequence
- This is normally n = 1 or 0 but it could be any integer
  - For example: To prove $u_{n} = 3^{n} - 2$ is the position-to-term formula for the recursive sequence $u_{n + 1} = 3 u_{n} + 4, u_{1} = 1$ :
  - $u_{1} = 3^{1} - 2 = 1$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $u_{k} = 3^{k} - 2$ is true
- There is nothing to do for this step apart from writing down the assumption
STEP 3: The inductive step
- Using the assumption show the result is true for n = k + 1
- It can be helpful to write down what you want to show
- The assumption from STEP 2 will be needed at some point
  - For example: Want to show $u_{k + 1} = 3^{k + 1} - 2$
- The trick to this step is to use the recursive relation formula:
  - $u_{k + 1} = 3 u_{k} + 4$

STEP 4: The conclusion step
- State the result is true
- Explain in words why the result is true
- It must include:
  - If true for n = k then it is true for n = k + 1
  - Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1 by mathematical induction
- The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

A sequence is defined by $u_{n + 1} = 5 u_{n} - 4, u_{1} = 2$ for $n \geq 1$ .

Prove by mathematical induction that $u_{n} = 5^{n - 1} + 1$ for $n \geq 1$ .

9-1-2-edexcel-al-fm-cp-proof-by-induction-sequences-we

Proof by induction - series

What are the steps for proof by induction with series?

STEP 1: The basic step
- Show the result is true for the base case
- This is normally n = 1 or 0 but it could be any integer
  - For example: To prove $\sum_{r = 1}^{n} r^{2} = \frac{1}{6} n (n + 1) (2 n + 1)$ is true for all integers n ≥ 1 you would first need to show it is true for n = 1:
  - $\sum_{r = 1}^{1} r^{2} = \frac{1}{6} (1) ((1) + 1) (2 (1) + 1)$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $\sum_{r = 1}^{k} r^{2} = \frac{1}{6} k (k + 1) (2 k + 1)$ is true
- There is nothing to do for this step apart from writing down the assumption
STEP 3: The inductive step
- Using the assumption show the result is true for n = k + 1
- It can be helpful to simplify LHS & RHS separately and show they are identical
- The assumption from STEP 2 will be needed at some point
  - For example: $L H S = \sum_{r = 1}^{k + 1} r^{2}$ and $R H S = \frac{1}{6} (k + 1) ((k + 1) + 1) (2 (k + 1) + 1)$
- The trick to this step is to use:

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

STEP 4: The conclusion step
- State the result is true
- Explain in words why the result is true
- It must include:
  - If true for n = k then it is true for n = k + 1
  - Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1 by mathematical induction
- The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

Prove by induction that $\sum_{r = 1}^{n} r (r - 3) = \frac{1}{3} n (n - 4) (n + 1)$ for $n \in ℤ^{+}$ .

1-5-1-ib-aa-hl-proof-by-induction-we-solution

Proof by induction - divisibility

What are the steps for proof by induction for divisibility?

STEP 1: The basic step
- Show the result is true for the base case
- This is normally n = 1 or 0 but it could be any integer
  - For example: To prove $f (n) = 4^{n} - 1$ is divisible by 3 for all integers n ≥ 1 you would first need to show it is true for n = 1:
  - $f (1) = 4 - 1 = 3 = 3 (1)$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $f (k) = 4 - 1$ is divisible by 3
- There is nothing to do for this step apart from writing down the assumption
- The trick for this step is to write the expression as a multiple of the number
  - For example: $4^{k} - 1 = 3 p$ for some integer p
STEP 3: The inductive step
- Using the assumption show the result is true for n = k + 1
- The assumption from STEP 2 will be needed at some point
  - For example: Show that $f (k + 1) = 4^{k + 1} - 1$ is divisible by 3
- The trick to this step is to use:

$a^{k + 1} = a \times a^{k}$

For example: $f (k + 1) = 4 (4^{k}) - 1 = 4 (1 + 3 p) - 1 = 3 (4 p + 1)$
- Another trick is to show that $f (k + 1) - f (k)$ is divisible by the number
- Be careful with numbers like 6 as for these you can instead show it is divisible by both 3 and 2

STEP 4: The conclusion step
- State the result is true
- Explain in words why the result is true
- It must include:
  - If true for n = k then it is true for n = k + 1
  - Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1 by mathematical induction
- The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

Prove by induction that $f (n) = 6^{n} + 13^{n + 1}$ is divisible by 7 for all integers $n \geq 0$ .

9-1-2-edexcel-al-fm-cp-proof-by-induction-divisibility-we

Proof by induction - matrices

What are the steps for proof by induction with matrices?

STEP 1: The basic step
- Show the result is true for the base case
- This is normally n = 1 but it could be any integer
  - For example: To prove $M^{n} = (\begin{matrix} 2^{n} & 0 \\ 1 - 2^{n} & 1 \end{matrix})$ where $M = (\begin{matrix} 2 & 0 \\ - 1 & 1 \end{matrix})$ for $n \geq 1$ :
  - $(\begin{matrix} 2^{1} & 0 \\ 1 - 2^{1} & 1 \end{matrix}) = (\begin{matrix} 2 & 0 \\ - 1 & 1 \end{matrix})$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $M^{k} = (\begin{matrix} 2^{k} & 0 \\ 1 - 2^{k} & 1 \end{matrix})$ is true
- There is nothing to do for this step apart from writing down the assumption
STEP 3: The inductive step
- Using the assumption show the result is true for n = k + 1
- It can be helpful to write down what you want to show
- The assumption from STEP 2 will be needed at some point
  - For example: Want to show $M^{k} = (\begin{matrix} 2^{k + 1} & 0 \\ 1 - 2^{k + 1} & 1 \end{matrix})$
- The trick to this step is to use write:
  - $M^{k + 1} = M M^{k}$
  - The entries in the matrix can get messy so it can be clearer to write $M^{k + 1} = (\begin{matrix} a & b \\ c & d \end{matrix})$ and then find expressions for a, b, c, d on separate lines

STEP 4: The conclusion step
- State the result is true
- Explain in words why the result is true
- It must include:
  - If true for n = k then it is true for n = k + 1
  - Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1 by mathematical induction
- The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

The matrix $M$ is given by $M = (\begin{matrix} 2 & 2 \\ 0 & 1 \end{matrix})$ .

Prove, using mathematical induction, that $M^{n} = (\begin{matrix} 2^{n} & 2 (2^{n} - 1) \\ 0 & 1 \end{matrix})$ .

9-1-2-edexcel-al-fm-cp-proof-by-induction-matrices-we

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

I would just like to say a massive thank you for putting together such a brilliant, easy to use website.I really think using this site helped me secure my top gradesin science and maths. You really did save my exams! Thank you.

Beth
IGCSE Student

This website is soooo useful and I can’t ever thank you enough for organising questions by topic like this. Furthermore, the name of the website could not have been more appropriate as it literally did SAVE MY EXAMS!

Fathima
A Level Student

Incredible! SO worth my money, the revision notes have everything I need to know and are so easy to understand. I actually enjoy revising! It makes me feel a lot more confident for my GCSEs in a few months.

Kate
GCSE Student

Absolutely brilliant, both my girls used it for A levels and GCSE. It's saves on paper copies, also beneficial exam questions ranked from easy to hard. It's removed a lot of stress from the exams.

Sameera
Parent

Just to say that your resources are the best I have seen and I have been teaching chemistry at different levels for about 40 years

Mark
Chemistry Teacher

Excellent

Common Cases of Proof by Induction (Edexcel A Level Further Maths: Core Pure): Revision Note

Proof by induction - sequences

What are the steps for proof by induction with sequences?

Worked Example

Proof by induction - series

What are the steps for proof by induction with series?

Worked Example

Proof by induction - divisibility

What are the steps for proof by induction for divisibility?

Worked Example

Proof by induction - matrices

What are the steps for proof by induction with matrices?

Worked Example

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

Author: Dan Finlay

Reviewer: Lucy Kirkham