Welcome to the World of Mathematical Proof!
In your GCSEs and A-Level Maths, you’ve learned how to solve equations and find values. But in Further Mathematics, we go one step deeper. We don't just want to know if something works; we want to prove that it works for every single number, forever!
In this chapter, we are focusing on one of the most powerful tools in a mathematician's toolkit: Mathematical Induction. Don't worry if this seems a bit "out there" at first—once you see the pattern, it's like watching a row of dominos fall.
1. What is Mathematical Induction?
Imagine an infinite row of dominos. How can you be absolutely certain that every single domino will eventually fall? You need to know two things:
1. The first domino is pushed over.
2. If any one domino falls, it will definitely hit the next one.
This is exactly how Mathematical Induction works. It is a method of proof used to show that a statement is true for all positive integers \( n \) (where \( n = 1, 2, 3, ... \)).
The Four Essential Steps
To write a perfect proof, you should always follow these four steps. You can remember them with the mnemonic B.A.I.C. (pronounced like "Basic"):
1. Basis: Show the statement is true for the first value (usually \( n = 1 \)).
2. Assumption: Assume the statement is true for some arbitrary integer \( k \).
3. Inductive Step: Use your assumption to prove it must also be true for the next integer, \( k + 1 \).
4. Conclusion: Write a formal sentence to wrap everything up.
Quick Review: Induction doesn't just "test" numbers; it creates a logical chain that connects every number to the one before it.
2. Induction with Sums of Series
This is the most common way you'll see induction. We want to prove that adding up a list of numbers follows a specific formula.
Example: Sum of first \( n \) integers
Prove that \( \sum_{r=1}^{n} r = \frac{1}{2}n(n+1) \)
Step 1: Basis. Let \( n = 1 \).
Left Hand Side (LHS) = 1.
Right Hand Side (RHS) = \( \frac{1}{2}(1)(1+1) = 1 \).
LHS = RHS, so it is true for \( n = 1 \).
Step 2: Assumption. Assume the statement is true for \( n = k \):
\( \sum_{r=1}^{k} r = \frac{1}{2}k(k+1) \)
Step 3: Inductive Step. We want to show it's true for \( n = k + 1 \).
The sum of \( k+1 \) terms is just the (sum of \( k \) terms) + (the \( (k+1)^{th} \) term).
Using our assumption: \( \frac{1}{2}k(k+1) + (k+1) \).
Factor out \( (k+1) \): \( (k+1) [ \frac{1}{2}k + 1 ] \).
Simplify the bracket: \( (k+1) [ \frac{1}{2}(k + 2) ] \).
This gives: \( \frac{1}{2}(k+1)(k+2) \). This is exactly the original formula but with \( k+1 \) plugged in!
Step 4: Conclusion. "Since it is true for \( n=1 \) and, if true for \( n=k \), it is true for \( n=k+1 \), the statement is true for all \( n \in \mathbb{Z}^+ \) by mathematical induction."
Common Mistake: Forgetting to factorize! In Step 3, students often expand everything into a messy quadratic. It is almost always easier to factor out the common terms like \( (k+1) \).
3. Induction with Divisibility
Here, we prove that a complex-looking expression is always divisible by a certain number (like 3, 7, or 13).
How to "Speak" Divisibility
If we say a number \( f(n) \) is divisible by 7, we can write it as \( f(n) = 7M \), where \( M \) is just some integer.
The Trick
The goal is to look at the expression for \( f(k+1) \) and try to find a way to include the expression for \( f(k) \) inside it. This lets you use your Assumption.
Did you know? This method is used in computer science to verify that algorithms (like those used in your banking app) will always produce the right result regardless of how many times they run!
Key Takeaway: In divisibility proofs, you are looking to show that \( f(k+1) - f(k) \) is a multiple of the divisor, or that \( f(k+1) \) can be written as (Multiple of Divisor) + \( f(k) \).
4. Induction with Matrices
You can also use induction to find a general formula for the power of a matrix, like \( \mathbf{M}^n \).
Prerequisite Check
Before trying these, make sure you are comfortable with Matrix Multiplication. You will need to multiply \( \mathbf{M}^k \) (your assumption) by \( \mathbf{M} \) to find \( \mathbf{M}^{k+1} \).
Example Step-by-Step
If \( \mathbf{M} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \), prove \( \mathbf{M}^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} \).
1. Basis: Let \( n=1 \). \( \mathbf{M}^1 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \). True.
2. Assumption: Assume \( \mathbf{M}^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \).
3. Inductive Step: Find \( \mathbf{M}^{k+1} \) by calculating \( \mathbf{M}^k \times \mathbf{M} \).
\( \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} (1\times 1 + k\times 0) & (1\times 1 + k\times 1) \\ (0\times 1 + 1\times 0) & (0\times 1 + 1\times 1) \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix} \).
This matches the formula for \( n=k+1 \)!
Don't worry if this seems tricky at first! Matrix induction is actually often the most straightforward type because the multiplication rules are very rigid—just be careful with your arithmetic.
Final Summary and Tips
The Structure is Your Friend
Even if you get stuck on the algebra in the middle, you can often pick up method marks just for laying out the Basis and the Conclusion correctly. AQA examiners love a clear, logical structure.
Common Pitfalls to Avoid:
- Notation: Be careful to use \( k \) and \( n \) correctly. Use \( n \) for the general statement and \( k \) for the specific step in your proof.
- The Conclusion: Do not skip the final sentence. You must state that the proof is complete by the principle of mathematical induction.
- The Assumption: Make sure you actually use your assumption \( n=k \) during the inductive step. If you haven't used it, it's not a proof by induction!
Keep practicing! Induction is a skill that gets much easier once you've seen 5 or 10 different examples. You've got this!