Welcome to the World of Proof!
In your standard A Level Maths course, you’ve learned how to solve equations and use formulas. In Further Mathematics, we go one step deeper. We don't just want to know that something works; we want to prove it works for every single number, forever!
In this chapter of the Pure Core, we focus on a powerful technique called Mathematical Induction. It’s like a mathematical "domino effect" that allows us to prove statements for an infinite set of integers with just a few logical steps. Don't worry if it seems a bit abstract at first—once you see the pattern, it becomes a very satisfying "recipe" to follow.
1. The Logic of Mathematical Induction
Imagine a line of dominoes stretching out forever. How can you be absolutely certain that every single domino will fall? You only need to prove two things:
1. The first domino falls.
2. If any one domino falls, it will definitely knock over the next one.
If both are true, the whole line must fall! In maths, we use this same logic to prove things about positive integers (\(n = 1, 2, 3, ...\)).
The Four-Step Recipe
To write a formal proof by induction, you must follow these four steps every time:
- The Basis Step: Prove the statement is true for the smallest possible value of \(n\) (usually \(n = 1\)).
- The Assumption: Assume the statement is true for some arbitrary integer \(k\). (We call this the Inductive Hypothesis).
- The Inductive Step: Use your assumption to show that the statement must then be true for the next integer, \(n = k + 1\). This is the "heavy lifting" part of the proof!
- The Conclusion: Write a formal sentence to wrap it up. (See the template below).
Quick Review: The Conclusion Template
"Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), the result is true for all \(n \in \mathbb{Z}^+\) by mathematical induction."
2. Proofs with Matrices
One common application in the syllabus is proving formulas for powers of matrices. These are often the easiest induction proofs because the algebra is very straightforward.
Example: Prove that \( \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^n = \begin{pmatrix} 1 & 0 \\ n & 1 \end{pmatrix} \) for \(n \in \mathbb{Z}^+\).
Step 1 (Basis): Let \(n = 1\).
Left Hand Side: \( \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^1 = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \).
Right Hand Side: \( \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \).
The basis step is true.
Step 2 (Assumption): Assume true for \(n = k\): \( \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^k = \begin{pmatrix} 1 & 0 \\ k & 1 \end{pmatrix} \).
Step 3 (Inductive Step): We need to find the result for \(n = k + 1\).
\( \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{k+1} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^k \times \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \)
Using our assumption: \( = \begin{pmatrix} 1 & 0 \\ k & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \)
Multiply the matrices: \( = \begin{pmatrix} (1 \times 1 + 0 \times 1) & (1 \times 0 + 0 \times 1) \\ (k \times 1 + 1 \times 1) & (k \times 0 + 1 \times 1) \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ k+1 & 1 \end{pmatrix} \).
This is the target formula with \(n\) replaced by \(k+1\)!
Step 4 (Conclusion): Use the template from Section 1.
Key Takeaway: For matrix powers, \(M^{k+1}\) is always \(M^k \times M\). Use your assumption for \(M^k\) and just multiply!
3. Proofs of Divisibility
These proofs ask you to show that an expression, like \(7^n - 3^n\), is always divisible by a certain number (in this case, 4).
The Trick: The goal is to rewrite the expression for \(k+1\) in a way that includes the expression for \(k\).
Example: Prove \(f(n) = 7^n - 3^n\) is divisible by 4 for \(n \in \mathbb{Z}^+\).
Assume true for \(n=k\): \(7^k - 3^k = 4M\) (where \(M\) is some integer).
Consider \(f(k+1) = 7^{k+1} - 3^{k+1}\)
\( = 7(7^k) - 3(3^k) \)
Now, split the 7 into \((4 + 3)\):
\( = (4 + 3)7^k - 3(3^k) \)
\( = 4(7^k) + 3(7^k) - 3(3^k) \)
\( = 4(7^k) + 3(7^k - 3^k) \)
Substitute our assumption \(7^k - 3^k = 4M\):
\( = 4(7^k) + 3(4M) = 4(7^k + 3M) \).
Since the whole thing is multiplied by 4, it must be divisible by 4!
Common Mistake: Don't forget to state that your final bracketed term is an integer. Divisibility only counts if you aren't left with fractions!
4. Proofs of Inequalities
These can be the trickiest because you have to use "greater than" (\(>\)) or "less than" (\(<\)) logic instead of equals signs.
Memory Aid: The "Bridge" Method
In these proofs, you are often trying to show that \(A > C\). You might find it easy to show \(A > B\) using your assumption, and then you just need to explain why \(B > C\).
Example: Prove \(2^n > 2n\) for \(n \ge 3\), \(n \in \mathbb{Z}\).
Note: Here the Basis Step starts at \(n=3\).
Basis: \(2^3 = 8\), \(2(3) = 6\). Since \(8 > 6\), it's true.
Assume: \(2^k > 2k\).
Inductive Step: Look at \(n = k+1\).
LHS: \(2^{k+1} = 2 \times 2^k\).
From our assumption, \(2 \times 2^k > 2 \times (2k)\), so \(2^{k+1} > 4k\).
We want to show \(2^{k+1} > 2(k+1)\), which is \(2k + 2\).
Since we know \(2^{k+1} > 4k\), and for \(k \ge 3\), \(4k\) is definitely bigger than \(2k + 2\), the proof is complete!
Did you know?
Mathematical induction was first used implicitly by ancient Greeks, but it wasn't formally described until the 16th century by Francesco Maurolico. It is now one of the Peano Axioms, which are the fundamental rules that define what numbers actually are!
5. Summary and Common Pitfalls
Don't worry if this seems tricky at first! Induction is a very formal style of writing. If you get stuck, remember the goal of each step:
- Basis Step: Just a simple check. If this doesn't work, the statement is false!
- Assumption: This is your "free gift." You are allowed to treat this as a fact to help you later.
- Inductive Step: This is just algebra. Aim to reach an expression that looks like your original formula but with \(k+1\) inside.
Common Pitfalls to Avoid:
1. Algebraic slips: Especially in divisibility proofs (watch your minus signs!).
2. Vague Conclusions: Examiners look for the specific phrase "true for \(n=1\)" and "if true for \(n=k\) then true for \(n=k+1\)."
3. Not using the assumption: If you don't use your \(n=k\) assumption in the \(n=k+1\) step, it isn't a proof by induction!
Key Takeaway: Mathematical Induction proves a "chain reaction." If you can show the first step happens and that each step causes the next, you’ve proved the whole infinite chain!