Introduction: The Power of Mathematical Certainty
Welcome to the world of mathematical proof! In your previous maths studies, you might have found that a formula "just works" because your teacher said so or because it worked for the first few numbers. In Further Mathematics, we aren't satisfied with "it seems to work." We want to be 100% certain that a statement is true for every single whole number in existence, from 1 to infinity.
In this chapter, we focus on Mathematical Induction. Think of it as the "Domino Effect" of mathematics. If you can prove that the first domino falls, and that any falling domino will always knock over the one after it, you’ve proven that every single domino in the infinite line will eventually fall!
The Golden Recipe: The Four Steps of Induction
Mathematical Induction always follows the same four-step structure. If you memorize this "recipe," you’ve already won half the battle. Don't worry if the algebra looks scary at first—focus on the logic of the steps.
1. The Basis Step: Prove the statement is true for the very first value (usually \(n = 1\)). This is like checking that the first domino actually falls.
2. The Assumption: Assume the statement is true for a general case, \(n = k\). We call this the Inductive Hypothesis. We aren't proving it yet; we are just saying, "If it works for \(k\)..."
3. The Inductive Step: Use your assumption from Step 2 to prove the statement must also be true for the next value, \(n = k + 1\). This is the "knocking over the next domino" part.
4. The Conclusion: Write a formal sentence to wrap it up. This is essential for gaining full marks in the exam!
Quick Review: The Logic
If it works for 1, and the fact it works for \(k\) means it works for \(k+1\), then because it worked for 1, it must work for 2. Because it works for 2, it must work for 3... and so on forever!
Type 1: Summation of Series
One of the most common uses of induction is proving formulas for the sum of a sequence of numbers.
Example Context: Show that \( \sum_{r=1}^n r(r+1) = \frac{n(n+1)(n+2)}{3} \)
Step-by-Step Explanation:
1. Basis: Let \(n = 1\).
Left Hand Side (LHS): \(1(1+1) = 2\).
Right Hand Side (RHS): \( \frac{1(1+1)(1+2)}{3} = \frac{1 \times 2 \times 3}{3} = 2\).
LHS = RHS, so it's true for \(n = 1\).
2. Assumption: Assume \( \sum_{r=1}^k r(r+1) = \frac{k(k+1)(k+2)}{3} \).
3. Inductive Step: We want to find the sum for \(n = k+1\).
Trick: The sum of \(k+1\) terms is just the sum of \(k\) terms (which we assumed in Step 2) plus the \((k+1)^{th}\) term.
Sum for \(k+1\) = \( \frac{k(k+1)(k+2)}{3} + (k+1)((k+1)+1) \)
Now, factorize! Don't expand everything; look for common factors like \((k+1)\) and \((k+2)\).
Sum = \( (k+1)(k+2) [ \frac{k}{3} + 1 ] = (k+1)(k+2) [ \frac{k+3}{3} ] \).
This matches the target formula where \(n\) is replaced by \(k+1\)!
Common Mistake to Avoid: Students often try to expand the whole cubic equation. This usually leads to messy algebra and mistakes. Always try to factorize common terms out as early as possible!
Type 2: Divisibility Proofs
This type of proof shows that a formula will always result in a number that is divisible by a specific integer (e.g., a multiple of 4).
Example Context: Show that \( 3^{2n} + 11 \) is divisible by 4 for all \(n \geq 1\).
How to Think About It:
To prove something is divisible by 4, we want to show it can be written as \(4 \times (\text{something})\), where "something" is a whole number (integer).
The "Trick" in the Inductive Step:
When you look at the case for \(k+1\), you will have \(3^{2(k+1)} + 11\).
This is \(3^{2k} \times 3^2 + 11 = 9(3^{2k}) + 11\).
Now, use your assumption! If \(3^{2k} + 11 = 4M\) (where \(M\) is an integer), then \(3^{2k} = 4M - 11\).
Substitute this back: \( 9(4M - 11) + 11 = 36M - 99 + 11 = 36M - 88 \).
Since both 36 and 88 are multiples of 4, we can write this as \(4(9M - 22)\).
Bingo! It’s a multiple of 4.
Did you know? Divisibility proofs are like checking if a machine always produces even results. No matter how big the input \(n\) is, the output will always sit perfectly in the "4-times table."
Type 3: Matrix Powers
Further Maths introduces matrices, and induction is perfect for proving what happens when you multiply a matrix by itself \(n\) times.
Example Context: Show that \( \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}^n = \begin{pmatrix} 2n+1 & -4n \\ n & 1-2n \end{pmatrix} \)
Step-by-Step Strategy:
1. Base Case: Plug in \(n=1\). Does the matrix match? Yes.
2. Assumption: Assume the formula works for \( \mathbf{M}^k \).
3. Inductive Step: Calculate \( \mathbf{M}^{k+1} \) by doing \( \mathbf{M}^k \times \mathbf{M} \).
Use your assumed matrix for \( \mathbf{M}^k \) and the original matrix for \(\mathbf{M}\).
Multiply them using standard matrix multiplication (row by column).
After simplifying the algebra inside the result, you should see the formula with \(k+1\) substituted in.
Memory Aid: Matrix Multiplication
Remember: "Dive across the row and down the column." If you struggle with matrix multiplication, practice that first before attempting these proofs!
The Essential Conclusion
In the Edexcel exam, the wording of your conclusion matters. You should always aim for something like this:
"Since the result is true for \(n=1\), and if it is true for \(n=k\) it is shown to be true for \(n=k+1\), then the result is true for all \(n \in \mathbb{Z}^+\) by mathematical induction."
Don't worry if this seems tricky at first! Induction is a very formal way of thinking. The more you practice the algebraic "shuffling" in the inductive step, the more natural it will feel.
Summary Checklist
Key Takeaways:
- Induction is like a ladder: To reach the top, you need to step on the first rung (Basis) and ensure each rung leads to the next (Inductive Step).
- Basis Step: Always check \(n=1\).
- Assumption: "Assume true for \(n=k\)" is your most powerful tool—you must use it in the next step.
- Inductive Step: This is where the marks are. Use algebra to move from \(k\) to \(k+1\).
- Contexts: Be ready for Sums (\(\sum\)), Divisibility (\(k^{n} + a\)), and Matrices (\(\mathbf{M}^n\)).