Edexcel IAL - Further Pure Mathematics 1- 8.1 Proof by Mathematical Induction- Study notes - New syllabus
Edexcel IAL – Further Pure Mathematics 1- 8.1 Proof by Mathematical Induction -Study notes- New syllabus
Edexcel IAL – Further Pure Mathematics 1- 8.1 Proof by Mathematical Induction -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 8.1 Proof by Mathematical Induction
Proof by Mathematical Induction
Mathematical induction is a method used to prove that a statement is true for all positive integers \( n \).
It consists of three logical steps:
| Step | Meaning |
| 1. Base case | Show the statement is true for the first value of \( n \). |
| 2. Inductive hypothesis | Assume the statement is true for \( n=k \). |
| 3. Inductive step | Use this to prove it is true for \( n=k+1 \). |
If all three steps are satisfied, the statement is true for all positive integers.
(i) Induction for Summation Formulae
Example
Prove that
\( \sum_{r=1}^{n} r^3 = \dfrac{n^2(n+1)^2}{4} \)
▶️ Answer / Explanation
Base case \( n=1 \):
LHS \( = 1^3 = 1 \)
RHS \( = \dfrac{1^2(2)^2}{4} = 1 \)
So true for \( n=1 \).
Assume true for \( n=k \):
\( \sum_{r=1}^{k} r^3 = \dfrac{k^2(k+1)^2}{4} \)
For \( n=k+1 \):
\( \sum_{r=1}^{k+1} r^3 = \sum_{r=1}^{k} r^3 + (k+1)^3 \)
\( = \dfrac{k^2(k+1)^2}{4} + (k+1)^3 \)
\( = (k+1)^2\left(\dfrac{k^2}{4} + (k+1)\right) = (k+1)^2 \dfrac{(k+2)^2}{4} \)
\( = \dfrac{(k+1)^2(k+2)^2}{4} \)
This matches the formula with \( n=k+1 \). So the result is true for all \( n \).
(ii) Induction for Divisibility
Example
Prove that \( 3^{2n} + 11 \) is divisible by 4 for all positive integers \( n \).
▶️ Answer / Explanation
Base case \( n=1 \):
\( 3^2 + 11 = 9 + 11 = 20 \), which is divisible by 4.
Assume true for \( n=k \):
\( 3^{2k} + 11 \) is divisible by 4.
For \( n=k+1 \):
\( 3^{2(k+1)} + 11 = 9 \cdot 3^{2k} + 11 \)
\( = 9(3^{2k} + 11) – 88 \)
Both \( 9(3^{2k}+11) \) and 88 are divisible by 4, so their difference is also divisible by 4.
(iii) Induction for Recurrence Relations
Example
Given \( u_{n+1} = 3u_n + 4 \), \( u_1 = 1 \), prove that \( u_n = 3^n – 2 \).
▶️ Answer / Explanation
Base case \( n=1 \):
\( u_1 = 1 \), RHS \( = 3 – 2 = 1 \)
Assume true for \( n=k \):
\( u_k = 3^k – 2 \)
Then
\( u_{k+1} = 3u_k + 4 = 3(3^k – 2) + 4 = 3^{k+1} – 2 \)
(iv) Induction for Matrix Powers
Example
Show that
\( \begin{pmatrix} -2 & -1\\ 9 & 4 \end{pmatrix}^{n} = \begin{pmatrix} 1 – 3n & -n\\ 9n & 3n + 1 \end{pmatrix} \)
▶️ Answer / Explanation
Base case \( n=1 \):
Both sides give \( \begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix} \).
Assume true for \( n=k \):
\( A^k = \begin{pmatrix} 1 – 3k & -k\\ 9k & 3k + 1 \end{pmatrix} \)
Then
\( A^{k+1} = A^k A \)
Multiply and simplify to obtain the form with \( k+1 \).