Welcome to the World of Mathematical Proof!
In your previous maths journey, you've solved plenty of equations and found many answers. But have you ever stopped to ask: "How do we know this is ALWAYS true?" That is what proof is all about. It is the gold standard of truth. In this chapter, we will learn how to build solid arguments that leave no room for doubt.
Don't worry if this seems a bit abstract at first. Think of a proof like a court case: you need to present evidence in a logical order to convince the jury (the examiner!) that your conclusion is the only possible truth.
1. Simple Proof Methods: Deduction, Exhaustion, and Counter-examples
Before we get to the heavy-duty techniques, let's look at the tools you might already be familiar with from A Level Maths.
Proof by Deduction
This is the most direct way to prove something. You start from known facts and use logical steps to reach a conclusion.
Analogy: It’s like following a recipe. If you start with the right ingredients and follow the steps correctly, you are guaranteed to get the cake at the end!
Proof by Exhaustion
This means checking every single possible case. This only works when there are a limited (finite) number of cases to check.
Example: To prove that no square number between 1 and 20 ends in a 7, you would just list them: \(1, 4, 9, 16\). None end in 7. Proof finished!
Disproof by Counter-example
In mathematics, a "conjecture" is a guess that hasn't been proven yet. To prove a conjecture is false, you only need to find one single example where it doesn't work.
Analogy: If someone claims "All birds can fly," you just need to point at one penguin to prove them wrong. The penguin is your counter-example.
Quick Review: - Deduction: Logical "A to B" steps. - Exhaustion: Check every single possibility. - Counter-example: Find one case that fails to disprove a rule.
2. Proof by Contradiction
This is a clever "backdoor" method. Instead of proving something is true directly, you assume it’s false and show that this assumption leads to absolute nonsense (a contradiction).
The Step-by-Step Process:
1. Assume the opposite: If you want to prove \(P\) is true, start by saying "Assume \(P\) is false."
2. Use logic: Work through the math based on that assumption.
3. Find the "Nonsense": Eventually, you will hit a statement that is clearly impossible (like \(1 = 2\) or saying a number is both even and odd).
4. Conclude: Since your assumption led to nonsense, the assumption must be wrong. Therefore, the original statement must be true.
Common Mistake to Avoid: Make sure you clearly state your initial assumption at the very beginning. If you don't say what you are assuming is false, the rest of your logic won't make sense to the examiner!
Key Takeaway: Contradiction is the "Sherlock Holmes" method: "When you have eliminated the impossible, whatever remains, however improbable, must be the truth."
3. Mathematical Induction
This is one of the most powerful tools in Further Maths. We use it to prove that a formula works for all positive integers (\(n = 1, 2, 3, ...\)).
The Domino Analogy: Imagine an infinite line of dominoes. To prove they will all fall down, you need to show 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).
The Four Pillars of an Induction Proof:
1. Basis: Show the statement is true for the smallest possible value (usually \(n = 1\)).
2. Assumption: Assume the statement is true for \(n = k\).
3. Inductive Step: Use your assumption to prove the statement is true for \(n = k + 1\). This is where the main algebra happens!
4. Conclusion: Write down the formal "closing statement" (see below).
What will you be asked to prove?
The syllabus specifically mentions four areas for Induction:
A. Sums of Series
Proving formulas like \(\sum_{r=1}^{n} r^2 = \frac{1}{6}n(n+1)(2n+1)\).
Trick: In the \(k+1\) step, always remember that \(\sum_{r=1}^{k+1} = (\sum_{r=1}^{k}) + \text{the } (k+1)^{th} \text{ term}\).
B. Sequences
Proving a formula for the \(n^{th}\) term of a sequence defined by a recurrence relation.
Example: If \(u_1 = 0\) and \(u_{n+1} = u_n + 2n\), prove that \(u_n = n^2 - n\).
C. Powers of Matrices
Proving a formula for \(\mathbf{M}^n\).
Step: To get from \(\mathbf{M}^k\) to \(\mathbf{M}^{k+1}\), you simply multiply your assumed matrix \(\mathbf{M}^k\) by the original matrix \(\mathbf{M}\). Order matters in matrices, so keep them in the correct order!
D. Divisibility and de Moivre’s Theorem
You might be asked to prove that an expression like \(3^{2n} - 1\) is always divisible by 8, or prove de Moivre’s Theorem: \((\cos \theta + i \sin \theta)^n = \cos n\theta + i \sin n\theta\).
Did you know? Even though de Moivre's Theorem looks scary because of the complex numbers, the Induction steps are exactly the same as they are for simple numbers!
The "Golden Conclusion" (Memorize this!)
To get full marks, you should end your induction proof with a sentence like this:
"Since the result is true for \(n=1\), and if true for \(n=k\) it is shown to be true for \(n=k+1\), then by the principle of mathematical induction, it is true for all positive integers \(n\)."
Key Takeaway: Induction is a loop. Prove it starts (\(n=1\)) and prove it continues (\(k \to k+1\)).
Final Summary Tips
- Read the question carefully: If it says "Prove by induction," you MUST use that specific 4-step method.
- Show your working: In proof, the "answer" is usually given to you in the question. You are being marked on the logical steps you use to get there.
- Don't panic at the algebra: In the Inductive Step (\(k+1\)), the algebra can look messy. Take a deep breath, factorize where possible, and keep an eye on the "target" expression you are trying to reach.