Welcome to the World of Mathematical Proof!
In your previous math studies, you’ve used plenty of formulas. But have you ever wondered how we know those formulas work for every single number? That’s where Proof comes in. In this chapter of Unit FP1, we focus on a powerful technique called Mathematical Induction.
Think of it as the "Gold Standard" of truth. Instead of just testing a few numbers and guessing, you will learn how to build a logical ladder that reaches to infinity. Don't worry if it seems a bit abstract at first—once you see the pattern, it becomes very satisfying!
1. The Logic of Mathematical Induction
The best way to understand Mathematical Induction is the Domino Analogy. Imagine an infinite line of dominoes. How can you be 100% sure that every single domino will eventually fall? You only need to prove two things:
- The Base Case: You can knock over the first domino (\(n=1\)).
- The Inductive Step: If any domino falls (let's call it domino \(k\)), it is guaranteed to knock over the next one (domino \(k+1\)).
If both are true, then the first knocks the second, the second knocks the third, and so on, forever!
The Four Essential Steps
Every induction proof in your FP1 exam should follow this specific structure:
- Basis: Prove the statement is true for \(n = 1\).
- Assumption: Assume the statement is true for \(n = k\).
- Induction: Use your assumption to show it must be true for \(n = k + 1\).
- Conclusion: Write a formal sentence explaining that because it's true for \(n=1\) and true for \(n=k+1\) when true for \(n=k\), it is true for all positive integers \(n\).
Quick Review: Induction doesn't just "show" a pattern; it proves the pattern can never be broken.
2. Proof by Induction: Summation of Series
This is the most common type of question. You are usually given a formula for the sum of a series and asked to prove it.
Example: Prove that \(\sum_{r=1}^{n} r(r+1) = \frac{n(n+1)(n+2)}{3}\)
Step-by-Step Guide:
- Basis: Let \(n=1\). Left side: \(1(1+1) = 2\). Right side: \(\frac{1(2)(3)}{3} = 2\). It works!
- Assumption: Assume \(\sum_{r=1}^{k} r(r+1) = \frac{k(k+1)(k+2)}{3}\).
- Induction: We want to find the sum for \(n=k+1\).
The Trick: The sum of \(k+1\) terms is just the Sum of \(k\) terms + the \((k+1)^{th}\) term.
\(\sum_{r=1}^{k+1} = \frac{k(k+1)(k+2)}{3} + (k+1)(k+2)\)
Now, factor out the common bits: \((k+1)(k+2) [ \frac{k}{3} + 1 ]\)
This simplifies to \(\frac{(k+1)(k+2)(k+3)}{3}\), which is exactly our formula with \(k+1\) swapped in!
Common Mistake: Many students try to expand everything into long polynomial strings. Don't! Always look for common factors to make the algebra easier.
Key Takeaway: For summation proofs, the core logic is: \(S_{k+1} = S_k + \text{Term}_{k+1}\).
3. Proof by Induction: Divisibility
Here, we prove that an expression like \(3^{2n} + 11\) is always divisible by a certain number (in this case, 4).
The "Substitution" Method
Let \(f(n) = 3^{2n} + 11\).
To prove it's divisible by 4, we look at the difference: \(f(k+1) - f(k)\) or we try to express \(f(k+1)\) using \(f(k)\).
Example walkthrough:
\(f(k+1) = 3^{2(k+1)} + 11 = 3^{2k} \cdot 3^2 + 11 = 9(3^{2k}) + 11\).
We know from our assumption that \(3^{2k} = f(k) - 11\).
Substitute this in: \(f(k+1) = 9(f(k) - 11) + 11 = 9f(k) - 99 + 11 = 9f(k) - 88\).
Since both \(9f(k)\) and \(88\) are divisible by 4 (because \(f(k)\) is assumed to be divisible and \(88 = 4 \times 22\)), then \(f(k+1)\) must also be divisible by 4!
Did you know? This method is like showing that if you add a "jump" of 4 to a multiple of 4, you'll land on another multiple of 4.
Key Takeaway: In divisibility, your goal is to show \(f(k+1) = (\text{multiple of divisor}) \times f(k) + (\text{another multiple of divisor})\).
4. Proof by Induction: Sequences
Sometimes a sequence is defined by a rule telling you how to get the next term (a recurrence relation), like \(u_{n+1} = 3u_n + 4\). You might be asked to prove a "general formula" for the \(n^{th}\) term.
Step-by-Step Logic:
- Basis: Check if the formula gives the correct value for \(u_1\).
- Assumption: Assume the formula works for \(u_k\).
- Induction: Use the recurrence relation \(u_{k+1} = 3u_k + 4\) and substitute your assumed formula for \(u_k\).
- Simplify: If the result matches the general formula for \(n=k+1\), you've nailed it!
Encouragement: These are often the "friendliest" induction problems because the algebra is usually straightforward substitution.
5. Proof by Induction: Matrices
In FP1, you also apply induction to Matrix Products. You will prove that a matrix raised to the power of \(n\) results in a specific formula.
Example: Show that \(\begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix}^n = \begin{pmatrix} 1-3n & -n \\ 9n & 3n+1 \end{pmatrix}\)
The Process:
- Basis: Check \(n=1\). Does the formula match the original matrix?
- Assumption: Assume \(\mathbf{M}^k = \begin{pmatrix} 1-3k & -k \\ 9k & 3k+1 \end{pmatrix}\).
- Induction: Calculate \(\mathbf{M}^{k+1}\) by doing: \(\mathbf{M}^k \times \mathbf{M}\).
Crucial Tip: Order matters in matrices! Always do \(\mathbf{M}^k \times \mathbf{M}\) (where \(\mathbf{M}\) is the matrix for \(n=1\)).
Common Mistake: Forgetting how to multiply matrices! Remember: Row by Column. \((Row 1 \times Column 1)\), then \((Row 1 \times Column 2)\), and so on.
Key Takeaway: Matrix induction is just standard induction where the "algebra" is actually matrix multiplication.
Final Summary: The "Magic Sentence"
To get full marks in your Edexcel exam, you must finish your proof with a formal conclusion. Practice writing this out until you can do it in your sleep:
"Since the result is true for \(n=1\), and if it is true for \(n=k\) it is also true for \(n=k+1\), then by the process of mathematical induction the result is true for all \(n \in \mathbb{Z}^+\)."
Quick Review Checklist:
- Did I show the Basis case clearly?
- Did I state my Assumption for \(n=k\)?
- Did I use my Assumption in the \(n=k+1\) step?
- Is my algebra clear (factoring rather than expanding)?
- Did I include the formal concluding sentence?
Don't worry if the algebra feels heavy at first. Induction is a skill—the more "dominoes" you knock down in practice, the easier it gets!