Welcome to the World of Mathematical Proof!
In your GCSE and A-level Maths journey so far, you’ve used plenty of formulas. But how do we know they are always true? In Further Maths, we don't just "take someone's word for it"—we prove it! This chapter focuses on a powerful technique called Mathematical Induction. It’s like a logical superpower that lets you prove something is true for every single whole number, all the way to infinity.
The Big Idea: The Domino Analogy
Think of Mathematical Induction like a row of standing dominoes stretching out forever. To know that every domino will eventually fall, you only need to check two things:
1. The first domino actually falls over.
2. If any domino falls, it is guaranteed to knock over the next one.
If both are true, the whole line must fall! In maths, we use this same logic to prove statements about the number \(n\).
The Four-Step Recipe for Induction
Don't worry if this seems a bit abstract at first. Every proof by induction follows the exact same four steps. Master these, and you've mastered the chapter!
Step 1: The Basis Step (The First Domino)
Show the statement is true for the very first value, usually \(n = 1\). This is often just a simple calculation.
Step 2: The Assumption
We assume the statement is true for some random integer \(k\). We write this down clearly: "Assume true for \(n = k\)."
Step 3: The Inductive Step (The "Push")
This is where the magic happens. We use our assumption from Step 2 to prove the statement must also be true for the next number, \(n = k+1\). This is usually the part that requires some algebra.
Step 4: The Conclusion
You must write a formal concluding sentence. Think of this as the "mic drop" at the end of your proof. "Since it is true for \(n=1\) and true for \(n=k+1\) when assumed true for \(n=k\), it is true for all \(n \in \mathbb{Z}^+\) by mathematical induction."
Quick Review:
- Basis: Prove for \(n=1\).
- Assumption: Assume for \(n=k\).
- Induction: Prove for \(n=k+1\).
- Conclusion: Write the formal wrap-up.
Context 1: Sums of Series
You might be asked to prove a formula for adding up a sequence of numbers. For example, proving that the sum of the first \(n\) integers is \( \frac{1}{2}n(n+1) \).
The Trick: When doing the \(k+1\) step, always remember that:
Sum of \((k+1)\) terms = (Sum of \(k\) terms) + (the \((k+1)^{th}\) term)
You replace the "Sum of \(k\) terms" with the formula you assumed in Step 2!
Common Mistake: Forgetting to factorise at the end of the \(k+1\) step. Your goal is always to make your messy algebra look exactly like the original formula, but with \((k+1)\) instead of \(n\).
Context 2: Divisibility
This involves proving that an expression (like \(4^n + 2\)) is always divisible by a certain number (like 3) for all \(n\).
Example Analogy: If we want to prove something is a multiple of 5, we are trying to show it can be written as \(5 \times (\text{something})\).
Step-by-step for the Inductive Step:
1. Write out the expression for \(f(k+1)\).
2. Try to "extract" the expression for \(f(k)\) out of it.
3. Use your assumption to replace \(f(k)\) with a multiple of the divisor (e.g., \(5m\)).
4. Show the whole thing is now a multiple of that divisor.
Did you know? Divisibility proofs are very common in cryptography, which keeps your internet data safe!
Context 3: Powers of Matrices
You will also use induction to prove formulas for matrices raised to the power of \(n\), such as \(\mathbf{M}^n\).
The Process:
- Basis: Show the formula works for \(\mathbf{M}^1\).
- Inductive Step: Calculate \(\mathbf{M}^{k+1}\) by doing \(\mathbf{M}^k \times \mathbf{M}\).
- Use your assumption to plug in the matrix formula for \(\mathbf{M}^k\) and perform matrix multiplication. The result should match the formula for \(n=k+1\).
Memory Aid: Always multiply on the right (\(\mathbf{M}^k \mathbf{M}\)). While \(\mathbf{M} \mathbf{M}^k\) also works for powers, staying consistent helps avoid confusion in more complex matrix algebra!
Top Tips for Success
1. Keep your target in sight: Before you start the algebra for the \(k+1\) step, write down on a scrap of paper what the answer should look like. This gives you a goal to work towards.
2. Don't skip the conclusion: In an exam, the concluding statement is often worth a dedicated "accuracy mark." Even if your algebra gets messy, write the conclusion to pick up easy marks!
3. Use clear notation: Use \(\sum\) for sums and \(\mathbf{M}\) for matrices. Clear work makes it harder for you to make "silly" mistakes and easier for the examiner to give you marks.
Key Takeaway Summary
Mathematical Induction is a formal way of proving a statement is true for all positive integers. It relies on a Basis Case (\(n=1\)) and an Inductive Step (\(n=k \implies n=k+1\)). You need to be able to apply this to sums of series, divisibility rules, and powers of matrices. Practice the algebra, but never forget the logical structure!