Proof (Mathematical Induction for FP1)

Edexcel International A-Level Further Mathematics· FP1 8.1 (2018 Spec Issue 3)· 25 min read

1. The Mandatory 4-Step Induction Structure (Mark Scheme Aligned)★☆☆☆☆⏱ 5 min

✓ Calculator OK

📘 Definition

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.

Base Case: Verify the statement holds for the smallest valid value of n (usually n=1 for FP1 questions)
Assumption (Inductive Hypothesis): State that you assume the statement is true for n = k, where k is a positive integer
Inductive Step: Use the assumption for n=k to prove the statement holds for n = k+1, showing all working clearly
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.

📐 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.

2. Induction for Summation of Series★★☆☆☆⏱ 6 min

✓ Calculator OK

📐 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.

3. Induction for Divisibility Statements★★★☆☆⏱ 6 min

✓ Calculator OK

📘 Definition

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^{2 n} + 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^{2 k} + 11 = 4 m$ where $m$ is a positive integer, so $3^{2 k} = 4 m - 11$ .
3
Inductive step: For n=k+1, $f (k + 1) = 3^{2 (k + 1)} + 11 = 9 \times 3^{2 k} + 11$ . Substitute assumption:
4
$9(4m - 11) + 11 = 36m - 99 + 11 = 36m - 88 = 4(9m - 22)$
5
Since $9 m - 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.

4. Induction for General Sequence Terms★★★☆☆⏱ 4 min

✓ Calculator OK

📐 Worked Example

A sequence is defined by the recurrence relation $u_{n + 1} = 3 u_{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} = 3 u_{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.

5. Induction for Matrix Powers★★★★☆⏱ 4 min

✓ Calculator OK

📐 Worked Example

Let $A = (- 2 9 - 1 4)$ . Prove that for all positive integers n, $A^{n} = (1 - 3 n 9 n - n 3 n + 1)$ .

1
Base case: n=1. $A^{1} = (- 2 9 - 1 4)$ , which matches the RHS for n=1. True for n=1.
2
Assumption: Assume true for n=k: $A^{k} = (1 - 3 k 9 k - k 3 k + 1)$ .
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.

6. Common Pitfalls

Wrong move:

Skipping the explicit concluding statement

Why:

The conclusion is a mandatory 1 mark on all induction questions per the Edexcel mark scheme

Correct move:

Write the full standard conclusion linking the base case, inductive step, and generalisation to all valid n

Wrong move:

Failing to confirm the factor is an integer in divisibility proofs

Why:

Examiners require confirmation that the expression is a whole multiple of the divisor, not just an algebraic multiple

Correct move:

Explicitly state that the resulting factor after rearrangement is an integer, so divisibility holds

Wrong move:

Using n=0 as the base case for positive integer n questions

Why:

The base case must align with the domain given in the question, which is almost always positive integers for FP1

Correct move:

Use the smallest n specified in the question as your base case, usually n=1

Wrong move:

Skipping intermediate steps in matrix multiplication

Why:

Partial marks are awarded for correct multiplication steps, even if the final result is wrong

Correct move:

Write out each element calculation explicitly when multiplying matrices for the inductive step

Wrong move:

Failing to clearly show substitution of the inductive hypothesis

Why:

Examiners need to see that you are using the n=k assumption to prove n=k+1, not just rearranging directly

Correct move:

Explicitly note when you substitute the inductive hypothesis into your working

7. Quick Reference 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^{4 n} - 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} = 2 u_{n} - 1$ , $u_{1} = 3$
Matrix Powers	Multiply assumed $A^{k}$ by A, simplify entries to match n=k+1 RHS	Prove $(1011)^{n} = (10 n 1)$
All Types	Full mandatory conclusion required for 1 mark	All induction questions require the standard concluding sentence

8. Frequently Asked

Do I get marks for writing the induction conclusion?

Yes! The explicit concluding statement is worth 1 mark on every FP1 induction question, per the official mark scheme. You must state it links the base case, inductive step, and generalises to all valid n.

Can I use n=0 as my base case?

Only if the question specifies the result holds for non-negative integers. For almost all FP1 questions, the base case is n=1 for positive integers.

What if I get stuck on the inductive step for divisibility?

Rearrange the n=k+1 expression to isolate the n=k assumed term, then show the remaining part is an integer multiple of the divisor.

Going deeper

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.