Welcome to the World of Mathematical Proof!
In your previous math studies, you’ve likely noticed patterns that seem to work for every number you try. But in Further Pure Mathematics 1 (FP1), "it seems to work" isn't good enough! We need to be 100% certain. This chapter focuses on Mathematical Induction—a powerful technique used to prove that a statement is true for every single positive integer (\(n = 1, 2, 3, ...\)) without having to check them one by one (which would take forever!).
Why is this important?
Think of it like a never-ending row of dominoes. If you can prove the first one falls, and you can prove that *if* any one domino falls, it *must* knock over the next one, then you know for a fact that every single domino in the line will eventually fall. That’s the heart of Induction!
Did you know?
Mathematical induction was used as far back as the 10th century, but it was formally developed in the 19th century. It is the "gold standard" for proving formulas in computer science and advanced logic.
Quick Review of Prerequisite Terms:
• Integers: Whole numbers (we usually focus on positive integers, \(n \in \mathbb{Z}^+\)).
• Summation (\(\sum\)): A shorthand for adding up a sequence of numbers.
• Matrices: Grids of numbers (used in the final part of this chapter).
1. The Four-Step Recipe for Proof by Induction
Don't worry if this seems tricky at first! Every induction proof follows the exact same "recipe." If you learn these four steps, you can solve almost any problem in this chapter.
Step 1: The Basis Step
Show the statement is true for the very first case, usually \(n = 1\). This is like checking that you can knock over the first domino.
Step 2: The Assumption
Assume the statement is true for some arbitrary number \(k\). We write this as "Assume true for \(n = k\)."
Step 3: The Inductive Step
This is the "engine" of the proof. Use your assumption from Step 2 to prove the statement is also true for the next number, \(n = k + 1\). This is like proving that if domino \(k\) falls, domino \(k+1\) must also fall.
Step 4: The Conclusion
You must write a formal concluding sentence. It’s like a "mic drop" that ties everything together.
Common Mistake to Avoid: Many students forget Step 1! Without the Basis Step, you might prove that "if it's true, then the next one is true," but if the first one never falls, the whole proof is useless.
2. Proof for Summation of Series
One of the most common uses of induction in FP1 is proving formulas for sums.
Example: Prove that \(\sum_{r=1}^{n} r = \frac{1}{2}n(n+1)\).
(Note: This is the formula for adding up all numbers from 1 to \(n\).)
Step 1 (Basis): Let \(n = 1\).
LHS (Left Hand Side) = 1.
RHS (Right Hand Side) = \(\frac{1}{2}(1)(1 + 1) = 1\).
LHS = RHS, so it's true for \(n = 1\).
Step 2 (Assumption): Assume the formula is true for \(n = k\):
\(\sum_{r=1}^{k} r = \frac{1}{2}k(k+1)\).
Step 3 (Inductive): We want to show it's true for \(n = k + 1\).
The sum up to \(k+1\) is just the sum up to \(k\) plus the next term (\(k+1\)):
\(\sum_{r=1}^{k+1} r = [\sum_{r=1}^{k} r] + (k+1)\)
Substitute our assumption from Step 2:
\(= \frac{1}{2}k(k+1) + (k+1)\)
Now, factorize out \((k+1)\):
\(= (k+1)[\frac{1}{2}k + 1]\)
\(= (k+1)[\frac{k + 2}{2}]\)
\(= \frac{1}{2}(k+1)(k+2)\)
This is exactly the original formula but with \((k+1)\) in place of \(n\). Success!
Step 4 (Conclusion): "Since the result is true for \(n=1\), and if true for \(n=k\) it is shown to be true for \(n=k+1\), the result is true for all \(n \in \mathbb{Z}^+\) by mathematical induction."
Key Takeaway: When doing series, the goal is always to add the \((k+1)\)-th term to your assumption and use algebra (usually factorizing) to make it look like the goal formula.
3. Proof for Divisibility
You might be asked to prove that an expression like \(3^{2n} + 11\) is always divisible by a certain number (in this case, 4).
The Trick: In the inductive step, you look at the expression for \(f(k+1)\) and try to split it into a part you know is divisible (from your assumption) and a second part that is obviously divisible.
Example Walkthrough:
1. Check \(n=1\): \(3^{2(1)} + 11 = 9 + 11 = 20\). Since 20 is \(4 \times 5\), it's true for \(n=1\).
2. Assume for \(n=k\): Assume \(3^{2k} + 11 = 4M\) (where \(M\) is some integer).
3. Check \(n=k+1\): \(f(k+1) = 3^{2(k+1)} + 11 = 3^{2k+2} + 11\).
Using power rules: \(3^{2k} \cdot 3^2 + 11 = 9(3^{2k}) + 11\).
Break the 9 into \((8 + 1)\):
\(= (8 \cdot 3^{2k}) + (1 \cdot 3^{2k} + 11)\).
The first part (\(8 \cdot 3^{2k}\)) is clearly divisible by 4. The second part (\(3^{2k} + 11\)) is divisible by 4 because of our assumption in Step 2! Therefore, the whole thing is divisible by 4.
Memory Aid: For divisibility, think "Split and Substitute." Split the term with the power to match your assumption.
4. Finding General Terms in a Sequence
Sometimes you are given a recurrence relation (where each term depends on the one before it, like \(u_{n+1} = 3u_n + 4\)) and a formula for the "general term" (\(u_n = 3^n - 2\)). You use induction to prove the general formula is correct.
How to handle it:
In the inductive step, you start with the recurrence relation \(u_{k+1} = 3u_k + 4\). Then, you replace \(u_k\) with your assumed formula and simplify to see if you get the formula for \(u_{k+1}\).
5. Matrix Products
This is a favorite exam topic! You are asked to prove a formula for the power of a matrix, such as \( \mathbf{A}^n \).
Prerequisite Check: Remember how to multiply a \(2 \times 2\) matrix? You multiply "Row by Column."
The Inductive Step for Matrices:
To find \(\mathbf{A}^{k+1}\), you simply calculate \(\mathbf{A}^k \times \mathbf{A}\).
1. Replace \(\mathbf{A}^k\) with the formula you assumed in Step 2.
2. Multiply it by the original matrix \(\mathbf{A}\).
3. Simplify the resulting four elements. They should match the goal formula with \((k+1)\) substituted in.
Quick Review Box:
• Series: Add the next term.
• Divisibility: Manipulate powers and "split" the expression.
• Sequences: Substitute the formula into the recurrence relation.
• Matrices: Multiply \(\mathbf{A}^k\) by \(\mathbf{A}\).
Final Summary: The "Secret Sauce"
Mathematical Induction isn't about solving an equation; it's about building a bridge. You show the bridge starts at \(n=1\), and you show that if the bridge reaches point \(k\), it can always reach point \(k+1\). If you do those two things, you've proved the bridge goes on forever!
Top Tip for the Exam: Even if you get stuck on the algebra in the middle of Step 3, always write out Step 1 and the formal conclusion in Step 4. You can pick up easy marks just for knowing the structure of the proof!