Proof by induction

Welcome to Proof by Induction!

Hello! Today we are diving into one of the most powerful tools in a mathematician's toolkit: Proof by Mathematical Induction. If you’ve ever wondered how we can be 100% certain that a mathematical formula works for every single number in existence without checking them one by one (which would take forever!), this is the chapter for you.

Don't worry if this seems a bit abstract at first. We are going to break it down into simple steps, use some helpful analogies, and look at exactly what you need for your Oxford AQA International AS Level Further Mathematics exams.

What is Proof by Induction?

Imagine a line of dominoes stretching out forever. How can you be sure that every single domino will eventually fall?
1. You need to make sure the first domino falls.
2. You need to make sure that if any domino falls, it is close enough to push over the next one.

If those two things are true, you don't need to walk down the line and check the millionth domino—you know it will fall! Mathematical induction works exactly the same way. We use it to prove that a statement is true for all positive integers \( n \) (where \( n = 1, 2, 3, \dots \)).

The Four-Step Recipe

Every proof by induction follows the same "recipe." If you follow these four steps, you can solve almost any problem in this chapter!

Step 1: The Basis (The First Domino)

First, we prove the statement is true for the smallest possible value of \( n \), which is usually \( n = 1 \).
Check the Left Hand Side (LHS) and the Right Hand Side (RHS) separately to see if they match.

Step 2: The Assumption (The "If" Step)

We assume the statement is true for some arbitrary integer \( k \).
This means we simply rewrite the formula, replacing \( n \) with \( k \). We call this our Inductive Hypothesis.

Step 3: The Inductive Step (The "Next" Domino)

This is where the math happens! We want to show that if the formula works for \( n=k \), it must also work for the next number, \( n = k+1 \).
Your goal is to use your "Assumption" from Step 2 to algebraically manipulate the expression until it looks exactly like the original formula, but with \( k+1 \) in it.

Step 4: The Conclusion (The Wrap-up)

You must finish with a standard sentence to get your final marks. It usually looks like this:
"Since the result is true for \( n=1 \), and if true for \( n=k \) it is also true for \( n=k+1 \), then by the principle of mathematical induction, it is true for all \( n \in \mathbb{Z}^+ \)."

Quick Review Box:
• Basis: Prove for \( n = 1 \).
• Assumption: Assume true for \( n = k \).
• Inductive Step: Prove true for \( n = k + 1 \).
• Conclusion: State the final logic.

Application 1: Summation of Series

In your syllabus (FP1.5), you learn about the sum of squares and cubes. Induction is often used to prove these formulas.

Example: Prove that \( \sum_{r=1}^{n} r = \frac{1}{2}n(n+1) \).
1. Basis: For \( n=1 \), LHS is 1. RHS is \( \frac{1}{2}(1)(2) = 1 \). True!
2. Assumption: Assume \( \sum_{r=1}^{k} r = \frac{1}{2}k(k+1) \).
3. Inductive Step: For \( n=k+1 \), the sum is \( (\text{sum up to } k) + (k+1) \text{ term} \).
Using our assumption: \( \frac{1}{2}k(k+1) + (k+1) \).
Factor 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 the original formula with \( k+1 \) instead of \( n \). Success!

Application 2: Matrix Powers

As seen in FPP1.1, you will work with matrices. Sometimes we need to prove a formula for a matrix raised to the power of \( n \), such as \( \mathbf{M}^n \).

The Trick: In the Inductive Step, remember that \( \mathbf{M}^{k+1} = \mathbf{M}^k \times \mathbf{M} \).
You use your Assumption for the \( \mathbf{M}^k \) part and then multiply it by the original matrix \( \mathbf{M} \) using standard matrix multiplication.

Application 3: Divisibility

You might be asked to prove that an expression like \( 7^n - 1 \) is always divisible by 6.

Did you know? This is like showing that a pattern of numbers always stays on the same "grid."
In the Inductive Step for divisibility, your goal is usually to rewrite the \( k+1 \) expression in a way that includes the \( k \) expression.
Example: To prove \( f(k+1) \) is divisible by 6, you might try to show that \( f(k+1) = f(k) + 6(\text{something}) \). Since we assumed \( f(k) \) is a multiple of 6, the whole thing must be a multiple of 6!

Common Mistakes to Avoid

1. Skipping the Basis Step: You must show \( n=1 \) works. You can't start a fire without a spark!
2. Circular Reasoning: Don't just say "it works for \( k+1 \) because the formula says so." You must algebraically reach the \( k+1 \) form using the \( k \) assumption.
3. Poor Conclusion: Exam boards are strict! Always write out the full concluding sentence to show you understand the logic.

Key Takeaways

1. Induction is for "All \( n \)" proofs: Use it when you see "for all positive integers \( n \)."
2. It’s a bridge: The Inductive Step is just building a bridge from the number \( k \) to the number \( k+1 \).
3. Practice the algebra: Most students find the "Step 3" algebra the hardest part. Practice factoring and expanding expressions—it's the key to making the sides match.

Don't worry if this feels like a lot of writing at first. Once you get the "flow" of the four steps, it becomes one of the most predictable and reliable marks in your Further Maths exam!