# Proof (Mathematical Induction for FP1)

> Edexcel International A-Level Further Mathematics · IAL Further Maths FP1
> Source: https://www.owlsprep.com/study/edexcel-ial-further-math-fp1-proof/

This guide covers proof by mathematical induction, the only proof method assessed in Edexcel IAL FP1 Further Maths. You will learn the standard 4-step mark scheme structure and apply it to the four required induction categories: summation, divisibility, sequences, matrices.

**Prerequisites:** [Algebraic manipulation and factorisation](https://www.owlsprep.com/study/edexcel-ial-maths-pure-algebra-manipulation/); [Summation notation use](https://www.owlsprep.com/study/edexcel-ial-maths-pure-sequences-series/); [Basic matrix arithmetic](https://www.owlsprep.com/study/edexcel-ial-further-math-fp1-matrices/); Recurrence relations for sequences

## Learning objectives

- Recall and apply the 4 mandatory mark-scheme aligned steps of proof by induction for Edexcel FP1
- Prove summation of finite series results using mathematical induction
- Prove divisibility statements for positive integer n using induction
- Prove general sequence terms and matrix power results using induction
- Write exam-compliant conclusions to secure all available marks for induction questions

## The Mandatory 4-Step Induction Structure (Mark Scheme Aligned)

**Proof by Mathematical Induction (FP1 Format)** — A deductive proof method used to show a statement holds for all positive integers n, with 4 mandatory steps that each earn separate marks on Edexcel FP1 exams.

1. **Base Case**: Verify the statement holds for the smallest valid value of n (usually n=1 for FP1 questions)
2. **Assumption (Inductive Hypothesis)**: State that you assume the statement is true for n = k, where k is a positive integer
3. **Inductive Step**: Use the assumption for n=k to prove the statement holds for n = k+1, showing all working clearly
4. **Conclusion**: Write the explicit standard conclusion: *True for n=1, and if true for n=k then true for n=k+1, therefore true for all positive integers n by mathematical induction*.

> **tip**
>
> The concluding sentence is a compulsory 1 mark on every induction question. Do not abbreviate or skip it, even if the rest of your proof is correct.

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

1. Base case: n=1. LHS = $\sum_{r=1}^1 r = 1$, RHS = $\frac{1}{2}(1)(2) = 1$. Statement holds for n=1.
2. Assumption: Assume true for n=k: $\sum_{r=1}^k r = \frac{1}{2}k(k+1)$.
3. Inductive step: For n=k+1, LHS = $\sum_{r=1}^{k+1} r = \sum_{r=1}^k r + (k+1)$. Substitute assumption:
4. $$\frac{1}{2}k(k+1) + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{1}{2}(k+1)(k+2)$$
5. This matches the RHS for n=k+1.
6. Conclusion: True for n=1, and if true for n=k then true for n=k+1, therefore true for all positive integers n by mathematical induction.

> **Exam tip:** Label each step of your proof clearly (Base Case, Assumption, Inductive Step, Conclusion) so examiners can easily award you all available marks.

*Calculator:* allowed

## Induction for Summation of Series

> **info**
>
> You may quote standard summation results (sum of r, sum of r², sum of r³) from the Edexcel Formula Book when constructing your inductive step, if needed. You do not need to prove these separately unless asked.

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

1. Base case: n=1. LHS = $1 \times 2 = 2$, RHS = $\frac{1}{3}(1)(2)(3) = 2$. True for n=1.
2. Assumption: Assume true for n=k: $\sum_{r=1}^k r(r+1) = \frac{1}{3}k(k+1)(k+2)$.
3. Inductive step: For n=k+1, LHS = $\sum_{r=1}^{k+1} r(r+1) = \sum_{r=1}^k r(r+1) + (k+1)(k+2)$. Substitute assumption:
4. $$\frac{1}{3}k(k+1)(k+2) + (k+1)(k+2) = (k+1)(k+2)\left(\frac{k}{3} + 1\right) = \frac{1}{3}(k+1)(k+2)(k+3)$$
5. This matches the RHS for n=k+1.
6. Standard concluding statement applies.

> **Exam tip:** Always expand or factorise your inductive step result to match the exact form of the RHS for n=k+1, not just a mathematically equivalent form, to ensure you get full marks.

*Calculator:* allowed

## Induction for Divisibility Statements

**Divisibility Induction Rule (FP1)** — For proofs that $f(n)$ is divisible by $d$, rearrange $f(k+1)$ into the form $m \times d + f(k)$ where $m$ is an integer, so if $f(k)$ is divisible by $d$, $f(k+1)$ is also divisible by $d$.

**Worked example:** Prove that for all positive integers n, $3^{2n} + 11$ is divisible by 4.

1. Base case: n=1. $3^2 + 11 = 20 = 5 \times 4$, so divisible by 4. True for n=1.
2. Assumption: Assume true for n=k: $3^{2k} + 11 = 4m$ where $m$ is a positive integer, so $3^{2k} = 4m - 11$.
3. Inductive step: For n=k+1, $f(k+1) = 3^{2(k+1)} + 11 = 9 \times 3^{2k} + 11$. Substitute assumption:
4. $$9(4m - 11) + 11 = 36m - 99 + 11 = 36m - 88 = 4(9m - 22)$$
5. Since $9m - 22$ is an integer, $f(k+1)$ is divisible by 4.
6. Standard concluding statement applies.

> **Exam tip:** Always explicitly state that the resulting factor after rearrangement is an integer to confirm divisibility, this is a required step for full marks.

*Calculator:* allowed

## Induction for General Sequence Terms

**Worked example:** A sequence is defined by the recurrence relation $u_{n+1} = 3u_n + 4$ with $u_1 = 1$. Prove that for all positive integers n, $u_n = 3^n - 2$.

1. Base case: n=1. $u_1 = 3^1 - 2 = 1$, which matches the given initial value. True for n=1.
2. Assumption: Assume true for n=k: $u_k = 3^k - 2$.
3. Inductive step: For n=k+1, use the recurrence relation: $u_{k+1} = 3u_k + 4$. Substitute assumption:
4. $$3(3^k - 2) + 4 = 3^{k+1} - 6 + 4 = 3^{k+1} - 2$$
5. This matches the formula for n=k+1.
6. Standard concluding statement applies.

> **Exam tip:** Always check the base case against the given initial term, not the formula you are proving, to confirm you have the correct starting point.

*Calculator:* allowed

## Induction for Matrix Powers

**Worked example:** Let $A = \begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix}$. Prove that for all positive integers n, $A^n = \begin{pmatrix} 1-3n & -n \\ 9n & 3n+1 \end{pmatrix}$.

1. Base case: n=1. $A^1 = \begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix}$, which matches the RHS for n=1. True for n=1.
2. Assumption: Assume true for n=k: $A^k = \begin{pmatrix} 1-3k & -k \\ 9k & 3k+1 \end{pmatrix}$.
3. Inductive step: For n=k+1, $A^{k+1} = A^k \times A$. Substitute assumption and multiply matrices:
4. $$\begin{pmatrix} 1-3k & -k \\ 9k & 3k+1 \end{pmatrix} \begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix} = \begin{pmatrix} (1-3k)(-2) + (-k)(9) & (1-3k)(-1) + (-k)(4) \\ 9k(-2) + (3k+1)(9) & 9k(-1) + (3k+1)(4) \end{pmatrix}$$
5. $$= \begin{pmatrix} -2 - 3k & -1 -k \\ 9k + 9 & 3k + 4 \end{pmatrix} = \begin{pmatrix} 1-3(k+1) & -(k+1) \\ 9(k+1) & 3(k+1)+1 \end{pmatrix}$$
6. This matches the RHS for n=k+1.
7. Standard concluding statement applies.

> **Exam tip:** Show all matrix multiplication steps explicitly, do not skip intermediate calculations, as partial marks are awarded for correct working even if you make an arithmetic error.

*Calculator:* allowed

## Common pitfalls

- **Wrong:** Skipping the explicit concluding statement
  - Why it fails: The conclusion is a mandatory 1 mark on all induction questions per the Edexcel mark scheme
  - Correct: Write the full standard conclusion linking the base case, inductive step, and generalisation to all valid n
- **Wrong:** Failing to confirm the factor is an integer in divisibility proofs
  - Why it fails: Examiners require confirmation that the expression is a whole multiple of the divisor, not just an algebraic multiple
  - Correct: Explicitly state that the resulting factor after rearrangement is an integer, so divisibility holds
- **Wrong:** Using n=0 as the base case for positive integer n questions
  - Why it fails: The base case must align with the domain given in the question, which is almost always positive integers for FP1
  - Correct: Use the smallest n specified in the question as your base case, usually n=1
- **Wrong:** Skipping intermediate steps in matrix multiplication
  - Why it fails: Partial marks are awarded for correct multiplication steps, even if the final result is wrong
  - Correct: Write out each element calculation explicitly when multiplying matrices for the inductive step
- **Wrong:** Failing to clearly show substitution of the inductive hypothesis
  - Why it fails: Examiners need to see that you are using the n=k assumption to prove n=k+1, not just rearranging directly
  - Correct: Explicitly note when you substitute the inductive hypothesis into your working

## Cheatsheet

| Induction Type | Key Step Reminder | Common Exam Example |
| --- | --- | --- |
| Summation of Series | Split sum into n=k sum + (k+1)th term, factorise to match n=k+1 RHS | Prove $\sum_{r=1}^n r^3 = \frac{1}{4}n^2(n+1)^2$ |
| Divisibility | Rearrange f(k+1) to $m \times d + f(k)$, confirm m is integer | Prove $2^{4n} - 1$ is divisible by 15 |
| Sequence Terms | Use given recurrence relation with assumed $u_k$ to derive $u_{k+1}$ | Prove $u_n = 2^n +1$ for $u_{n+1}=2u_n -1$, $u_1=3$ |
| Matrix Powers | Multiply assumed $A^k$ by A, simplify entries to match n=k+1 RHS | Prove $\begin{pmatrix}1&1\\0&1\end{pmatrix}^n = \begin{pmatrix}1&n\\0&1\end{pmatrix}$ |
| All Types | Full mandatory conclusion required for 1 mark | All induction questions require the standard concluding sentence |

## What's next

Now that you have mastered proof by induction for Edexcel IAL FP1, you are ready to apply this foundational technique to more advanced Further Mathematics topics. Induction will reappear in FP2 for proving De Moivre's Theorem for general n, and in other units, so consolidating your understanding of the 4-step structure now will save you time later. Practice a mix of all four induction types from past WFM01 papers to build speed and accuracy, and always ensure you write the full concluding statement to secure all available marks. Pay close attention to avoiding the common pitfalls outlined in this guide, especially arithmetic errors in matrix multiplication or algebraic manipulation.

---

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/edexcel-ial-further-math-fp1-proof/