Welcome to the World of Mathematical Proof!
In your GCSE and A Level studies, you’ve used plenty of formulas. But have you ever wondered how we know they are true for every single number? In Further Mathematics, we don't just "take someone's word for it." We use Mathematical Induction.
Think of Mathematical Induction like a line of dominoes. To knock them all down, you only need to do two things:
1. Knock down the first domino.
2. Ensure that if any domino falls, it must knock down the next one.
If you prove these two things, you know the whole line will fall, even if it goes on forever! That is exactly how we prove things for all positive integers \( n \).
The Four-Step Recipe for Success
Every proof by induction in your 8FM0 Core Pure exam should follow this same logical "recipe." Don't worry if it feels like a lot of writing at first—once you learn the pattern, it becomes much easier!
1. The Basis Step: Show the statement is true for the very first value (usually \( n = 1 \)).
2. The Assumption: Assume the statement is true for a general case, \( n = k \).
3. The Inductive Step: Use your assumption to prove the statement must be true for the next case, \( n = k + 1 \).
4. The Conclusion: Write down a formal sentence to wrap it all up.
Quick Review: Why do we assume it's true for \( k \)? We are checking the "connection" between one number and the next. If that connection exists, and the first one works, they all work!
1. Summation of Series
One of the most common ways you'll use induction is to prove formulas for adding up a list of numbers (series).
Example: Show that \( \sum_{r=1}^{n} r = \frac{1}{2}n(n+1) \)
Step 1: Basis. For \( n = 1 \), the Left Hand Side (LHS) is 1. The Right Hand Side (RHS) is \( \frac{1}{2}(1)(1+1) = 1 \). Since LHS = RHS, it is true for \( n = 1 \).
Step 2: Assumption. Assume the formula works for \( n = k \): \( \sum_{r=1}^{k} r = \frac{1}{2}k(k+1) \).
Step 3: Inductive Step. Look at \( n = k + 1 \). This is just the sum up to \( k \), plus the next term (\( k+1 \)).
\( \sum_{r=1}^{k+1} r = [\sum_{r=1}^{k} r] + (k+1) \)
Substitute your assumption: \( = \frac{1}{2}k(k+1) + (k+1) \)
Factor out \( (k+1) \): \( = (k+1)[\frac{1}{2}k + 1] \)
Simplify: \( = \frac{1}{2}(k+1)(k+2) \). This is exactly the original formula with \( k+1 \) swapped in for \( n \)!
Step 4: Conclusion. "Since the result is true for \( n=1 \) and, if true for \( n=k \), it is true for \( n=k+1 \), the result is true for all \( n \in \mathbb{Z}^+ \) by mathematical induction."
Memory Aid: Always factorize rather than expanding everything! Looking for a "common bracket" (like \( k+1 \) above) makes the algebra much friendlier.
2. Divisibility Proofs
This is where we prove that an expression is always divisible by a certain number. This can seem a bit abstract, so let’s use an analogy: If you have a box of 4 chocolates, any multiple of that box is still divisible by 4.
Example: Prove \( f(n) = 3^{2n} + 11 \) is divisible by 4.
The Trick: In the inductive step, we look at the difference between the next term and the current term: \( f(k+1) - f(k) \). If that difference is divisible by 4, and \( f(k) \) is divisible by 4, then \( f(k+1) \) must be too!
Step-by-Step for Inductive Step:
1. Find \( f(k+1) \): \( 3^{2(k+1)} + 11 = 3^{2k+2} + 11 \).
2. Rewrite using powers: \( 3^2 \times 3^{2k} + 11 = 9(3^{2k}) + 11 \).
3. Use a "substitution" or "difference" method. For example: \( f(k+1) - f(k) = [9(3^{2k}) + 11] - [3^{2k} + 11] \).
4. Simplify: \( 8(3^{2k}) \). Since 8 is a multiple of 4, this whole expression is divisible by 4!
Common Mistake: Students often forget to explicitly state that \( 8(3^{2k}) \) is \( 4 \times 2(3^{2k}) \). Always show the number you are dividing by as a factor!
3. Matrix Powers
The syllabus requires you to prove formulas for \( \mathbf{M}^n \). This is often the most straightforward type if you are comfortable with matrix multiplication.
Prerequisite Check: To multiply \( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \times \begin{pmatrix} e & f \\ g & h \end{pmatrix} \), you go "Across the Row and Down the Column."
The Inductive Step logic: To get \( \mathbf{M}^{k+1} \), you simply calculate \( \mathbf{M}^k \times \mathbf{M} \).
1. Assume the formula for \( \mathbf{M}^k \) is true.
2. Multiply that assumed matrix by the original matrix \( \mathbf{M} \).
3. Simplify the result until it looks like the target formula with \( k+1 \) in it.
Did you know? Matrix induction proofs are very common in computer graphics. We use matrices to rotate shapes; induction proves that repeating a small rotation \( n \) times follows a predictable path!
Common Pitfalls to Avoid
• Bad Notation: Don't just write "LHS = RHS." Clearly show the substitution for \( n=1 \).
• The "Assumption" Step: You must write "Assume the result is true for \( n=k \)." If you don't assume it, you can't use it!
• Vague Conclusions: The conclusion is worth a mark. Use the formal wording: "True for \( n=1 \)... if true for \( n=k \)... true for \( n=k+1 \)... therefore true for all \( n \)."
Key Takeaway Summary
• Induction is a 4-step process: Basis, Assumption, Inductive Step, Conclusion.
• Summation: Focus on factoring out common terms in the algebra.
• Divisibility: Show that \( f(k+1) \) is a multiple of the divisor by using your assumption.
• Matrices: Use \( \mathbf{M}^{k+1} = \mathbf{M}^k \mathbf{M} \) and perform standard matrix multiplication.
Don't worry if this seems tricky at first! Proof is a new way of thinking. Practice the structure of the writing, and the math will start to fall into place like those dominoes!