Welcome to the World of Proof!
In your A Level Mathematics journey, you have already seen many formulas. But have you ever wondered how we know they work for every single number in existence? We can't test every number individually because we’d be here forever! This is where Mathematical Induction comes in. It is one of the most powerful tools in the "Pure Core" section of Further Mathematics. Think of it as the "Domino Effect" of math. If you can knock down the first domino and prove that any falling domino knocks down the next one, you’ve proven that every domino in the line will eventually fall.
What is Mathematical Induction?
Induction is a formal way of proving that a statement is true for all positive integers \(n\). Don't worry if it seems a bit abstract at first; once you learn the "rhythm" of the steps, it becomes much more manageable!
The Prerequisite Basics
Before we dive in, make sure you are comfortable with these symbols:
1. Summation Notation \(\sum\): This means "the sum of."
2. Factorials \(n!\): For example, \(4! = 4 \times 3 \times 2 \times 1 = 24\).
3. Matrix Powers: Multiplying a matrix by itself \(n\) times.
The Four Steps to Success
Every induction proof follows the exact same 4-step structure. You can remember them with the mnemonic B.A.I.C. (pronounced like "Basic"):
1. Basis Case: Show the statement is true for the first value (usually \(n=1\)). This is like knocking over the very first domino.
2. Assumption: Assume the statement is true for some number \(k\). We write: "Assume true for \(n = k\)."
3. Inductive Step: This is the heart of the proof. Use your assumption from Step 2 to prove that the statement must also be true for the next number, \(k+1\). This is proving that if domino \(k\) falls, domino \(k+1\) must fall.
4. Conclusion: Write a formal closing statement to wrap it all up.
Quick Review: Always start by testing the smallest value of \(n\) mentioned in the question. If the question says \(n \ge 3\), your Basis Case is \(n=3\), not \(n=1\)!
Application 1: Sums of Series
In these problems, you are given a formula for the sum of a list of numbers and asked to prove it. For example: Prove that \(\sum_{r=1}^{n} r = \frac{1}{2}n(n+1)\).
In the Inductive Step, the trick is to realize that the sum up to \(k+1\) is just the sum up to \(k\) (which you already have a formula for!) plus the \((k+1)\)-th term.
\(S_{k+1} = S_k + \text{Term}_{k+1}\)
Application 2: Divisibility Proofs
The syllabus requires you to prove things like: "Show \(7^n - 3^n\) is divisible by 4."
The goal in the Inductive Step is to manipulate your expression for \(k+1\) until you can see a "chunk" that matches your assumption for \(k\).
Top Tip: If you are trying to prove something is divisible by 4, you are trying to show it equals \(4 \times (\text{something})\).
Application 3: Matrices
You might be asked to prove a formula for \(\mathbf{M}^n\).
The logic here is simple: \(\mathbf{M}^{k+1} = \mathbf{M}^k \times \mathbf{M}\).
You substitute your assumed matrix for \(\mathbf{M}^k\) and multiply it by the original matrix \(\mathbf{M}\). If the result matches the formula with \(k+1\) plugged in, you've done it!
Application 4: Inequalities (The Demanding Stuff)
Sometimes you need to prove things like \(2^n > 2n\) for \(n \ge 3\). These are trickier because you aren't looking for an "equals" sign.
The Logic: If you know \(A > B\) and you can show \(B > C\), then you have successfully proven \(A > C\). This is often called the Transitive Property.
Did you know? There is a famous inequality called Bernoulli’s Inequality which states \((1+x)^n \ge 1+nx\) for \(x > -1\). You might be asked to prove this using induction!
Application 5: Differentiation
You can even use induction for calculus! The syllabus mentions proving the \(n\)-th derivative of a function. For example, finding the \(n\)-th derivative of \(x^2 e^x\).
In the Inductive Step, you take the \(k\)-th derivative (your assumption) and differentiate it one more time to get the \((k+1)\)-th derivative.
Conjecture and Proof
A conjecture is just a fancy word for an "educated guess." Sometimes an exam question will ask you to:
1. Work out the first few terms (e.g., \(n=1, 2, 3\)).
2. Conjecture (guess) a general formula.
3. Use Induction to prove your guess is right.
Common Mistakes to Avoid
1. Forgetting the Basis Case: You can't have a domino effect if no one knocks over the first domino!
2. Circular Reasoning: You cannot use the formula for \(k+1\) to prove the formula for \(k+1\). You must start with the formula for \(k\) and work forward.
3. Poor Algebra: Most students struggle with the algebra in the Inductive Step. Take your time and use brackets carefully!
4. Vague Conclusions: You must write the full conclusion. It might feel repetitive, but it earns you the final mark.
The "Golden" Conclusion Template
"Since the statement is true for \(n=1\), and if true for \(n=k\) it is shown to be true for \(n=k+1\), then by the principle of mathematical induction, the statement is true for all \(n \in \mathbb{Z}^+\)."
Summary Takeaway
Basis: Prove it works for the start.
Assumption: Pretend it works for a random point \(k\).
Induction: Prove that working for \(k\) forces it to work for \(k+1\).
Conclusion: State that it works for everyone!
Don't worry if this seems tricky at first! Induction is a very formal "game." The more you practice the layout, the more natural the algebra will feel. You are essentially learning to build a logical ladder that reaches infinity!