Proof by induction

Welcome to the World of Mathematical Induction!

Ever wondered how mathematicians can be 100% sure that a formula works for every single number up to infinity? They don't just test it a million times and hope for the best! Instead, they use a powerful "domino effect" logic called Proof by Induction.

In this chapter of Further Pure Mathematics 1, you will learn how to build these logical "domino runs" to prove patterns in sums, divisibility, matrices, and even calculus. Don't worry if this seems a bit abstract at first—once you master the four standard steps, you'll find it’s one of the most satisfying parts of Further Maths!

1. The Logic: The Domino Analogy

Imagine a line of dominoes stretching forever. To prove they will all fall down, you only need to prove two things:
1. The first domino falls (the Base Case).
2. If any domino falls, it will definitely knock over the next one (the Inductive Step).

If both are true, the whole line must fall! In maths, we use this to prove a statement \(P(n)\) is true for all positive integers \(n \ge 1\).

2. The Four Essential Steps

Every induction proof follows the exact same structure. Follow these like a recipe:

Step 1: The Base Case
Show the statement is true for the smallest possible value (usually \(n = 1\)). Substitute \(n = 1\) into both sides of your equation and show they match.

Step 2: The Assumption
Assume the statement is true for some integer \(k\). We write: "Assume \(P(k)\) is true for some \(k \in \mathbb{Z}^+\)."

Step 3: The Inductive Step
This is the "engine room" of the proof. You must use your assumption from Step 2 to prove the statement is true for \(n = k + 1\). Your goal is to reach the target expression where every \(k\) is replaced by \((k+1)\).

Step 4: The Conclusion
Write a formal closing statement. "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, the result is true for all \(n \in \mathbb{Z}^+\)."

Key Takeaway:

Never skip the conclusion! It carries marks in the exam for completing the logical argument.

3. Type 1: Summation of Series

This is the most common type. You are given a sum formula, like the one in your syllabus:
\(\sum_{r=1}^{n} r^3 = \frac{1}{4}n^2(n+1)^2\)

The Trick:
To get from the sum of \(k\) terms to the sum of \(k+1\) terms, you just add the next term:
Sum of \((k+1)\) terms = (Sum of \(k\) terms) + (\((k+1)\)-th term)

Step-by-step for Sums:
1. Prove \(n=1\).
2. Assume \(\sum_{r=1}^{k} r^3 = \frac{1}{4}k^2(k+1)^2\).
3. Add the \((k+1)\)-th term, which is \((k+1)^3\), to your assumption:
\(\frac{1}{4}k^2(k+1)^2 + (k+1)^3\)
4. Important: Do not expand everything! Factor out the common term \((k+1)^2\) immediately. This makes the algebra much easier.

Quick Review Box:
Common error: Forgetting to replace \(n\) with \((k+1)\) in the entire formula. If your formula has \((n+1)\), the target for the inductive step is \(((k+1)+1)\), which is \((k+2)\).

4. Type 2: Divisibility Proofs

Here, you prove that an expression like \(f(n) = 3^{2n} + 2 \times 5^n - 3\) is always divisible by a certain number (e.g., 8).

The Strategy:
Look at the difference \(f(k+1) - f(k)\) or try to express \(f(k+1)\) in terms of \(f(k)\).
If you can show \(f(k+1) = f(k) + (\text{something divisible by 8})\), you've won! Because we assumed \(f(k)\) is divisible by 8, then \(f(k+1)\) must be too.

Memory Aid: "The Factor Trick"
When working with \(f(k+1)\), you will get terms like \(3^{2(k+1)}\). Rewrite this as \(3^2 \times 3^{2k} = 9 \times 3^{2k}\). Then, write \(9\) as \((8 + 1)\). This "pulls out" the divisor you are looking for!

Did you know?
Divisibility proofs are often used in computer science to ensure that algorithms handling large numbers won't crash due to unexpected remainders!

5. Type 3: Matrix Powers

The syllabus requires you to prove results for \(\mathbf{M}^n\) where \(\mathbf{M}\) is a \(2 \times 2\) matrix.
Example: Prove \(\begin{pmatrix} 4 & -1 \\ 6 & -1 \end{pmatrix}^n = \begin{pmatrix} 3 \times 2^n - 2 & 1 - 2^n \\ 3 \times 2^{n+1} - 6 & 3 - 2^{n+1} \end{pmatrix}\)

The Inductive Step for Matrices:
Use the rule: \(\mathbf{M}^{k+1} = \mathbf{M} \times \mathbf{M}^k\).
1. Substitute your Assumption matrix for \(\mathbf{M}^k\).
2. Multiply it by the Original matrix \(\mathbf{M}\).
3. Use your algebra skills to simplify the results until they look like the formula for \(n=k+1\).

Key Takeaway:

Matrix multiplication is not commutative (\(\mathbf{AB} \neq \mathbf{BA}\) usually), but for induction, \(\mathbf{M} \times \mathbf{M}^k\) and \(\mathbf{M}^k \times \mathbf{M}\) will give the same result. Stick to \(\mathbf{M} \times \mathbf{M}^k\) to be consistent.

6. Type 4: Sequences and Conjectures

Sometimes you aren't given the formula. You have to find it first! This is called a Conjecture.

Example: Finding the \(n\)-th derivative of \(xe^x\).
1. Find the 1st derivative: \(f'(x) = e^x + xe^x = (x+1)e^x\).
2. Find the 2nd derivative: \(f''(x) = e^x + (x+1)e^x = (x+2)e^x\).
3. Spot the pattern: It looks like \(f^{(n)}(x) = (x+n)e^x\).
4. Prove it: Use induction to show your "guess" (conjecture) is actually correct for all \(n\).

Common Mistake to Avoid:
When dealing with sequences like \(u_{n+1} = 3u_n - 1\), students sometimes forget to use the recurrence relation in the inductive step. Always look for where you can sub in the "rule" of the sequence!

Summary Checklist for Success

• Base Case: Did I clearly show \(LHS = RHS\) for \(n=1\)?
• Assumption: Did I write "Assume true for \(n=k\)"?
• Inductive Step: Did I actually use the assumption? (If you didn't use it, it’s not an induction proof!)
• Algebra: Am I factoring instead of expanding everything into a mess?
• Conclusion: Did I write the "Since it's true for \(n=1\)..." paragraph?

Don't be discouraged if the algebra gets messy at first. Induction is a test of patience as much as logic. Keep your target (\(n=k+1\)) in mind, and you'll get there!