Welcome to the World of Mathematical Proof!
In your math journey so far, you’ve solved plenty of equations and drawn many graphs. But have you ever stopped to ask, "How do we know this is always true?"
That is where Proof comes in. In this chapter of Unit P2, you will learn how to move from "it looks like it works" to "it 100% must be true." Think of yourself as a mathematical lawyer—you aren't just guessing; you are building a case using logic that no one can argue with!
1. The Structure of a Mathematical Proof
A proof is a logical argument that shows a statement is true for every possible case. It follows a very specific path:
- Assumptions: Start with what you already know is true (definitions or facts).
- Logical Steps: Use algebra or logic to move from one step to the next.
- Conclusion: End with the statement you were trying to prove.
Prerequisite Concepts: Even and Odd Numbers
Before we start, you must know how to write even and odd numbers algebraically. This is a vital "trick" for your exams:
- An even number is always a multiple of 2. We write it as \( 2n \).
- An odd number is always one more (or one less) than an even number. We write it as \( 2n + 1 \) (or \( 2n - 1 \)).
Quick Review: To prove something is even, show it can be written as \( 2 \times (\dots) \). To prove it is odd, show it is \( 2 \times (\dots) + 1 \).
2. Proof by Exhaustion
Don't worry, this doesn't mean the math will make you tired! Proof by exhaustion simply means you "exhaust" all the possibilities. You break the problem down into every possible case and prove that the statement works for each one.
When to use it?
Use this method when there are only a limited number of cases to check.
Step-by-Step Example:
Question: Suppose \( x \) and \( y \) are odd integers greater than 0 and less than 7. Prove that their sum \( x + y \) is always divisible by 2.
Step 1: List all possibilities for \( x \) and \( y \).
The odd integers are {1, 3, 5}.
Step 2: Test every possible pair.
\( 1 + 1 = 2 \) (Divisible by 2)
\( 1 + 3 = 4 \) (Divisible by 2)
\( 1 + 5 = 6 \) (Divisible by 2)
\( 3 + 3 = 6 \) (Divisible by 2)
\( 3 + 5 = 8 \) (Divisible by 2)
\( 5 + 5 = 10 \) (Divisible by 2)
Step 3: Conclusion.
Since we have tested every possible case and the sum was always divisible by 2, the statement is proven by exhaustion.
Common Mistake: Forgetting to check a case. If the question says "\( x \) and \( y \)," it usually means they could be the same number (e.g., \( 1 + 1 \)) unless it says "distinct integers."
3. Disproof by Counter-Example
Sometimes, a mathematical statement is false. To prove a statement is false, you don't need to check every case. You only need to find one single example where it doesn't work. This is called a counter-example.
The "Black Swan" Analogy
If someone says, "All swans are white," you don't need to look at every white swan in the world to prove them right. But if you find just one black swan, you have proven their statement is wrong. That black swan is your counter-example!
Step-by-Step Example:
Question: Disprove the statement: "\( n^2 - n + 1 \) is a prime number for all positive integers \( n \)."
Step 1: Try small values of \( n \).
If \( n = 1 \): \( 1^2 - 1 + 1 = 1 \) (Note: 1 is not prime, so this is already a counter-example!)
If \( n = 2 \): \( 2^2 - 2 + 1 = 3 \) (Prime)
If \( n = 3 \): \( 3^2 - 3 + 1 = 7 \) (Prime)
If \( n = 5 \): \( 5^2 - 5 + 1 = 21 \)
Step 2: Identify the failure.
Look at \( n = 5 \). The result is 21. We know that \( 21 = 3 \times 7 \), so 21 is not a prime number.
Step 3: State the conclusion clearly.
When \( n = 5 \), \( n^2 - n + 1 = 21 \), which is not prime. Therefore, the statement is false by counter-example.
Did you know? You only need one counter-example to destroy a theory that has worked for millions of other cases!
4. Direct Proof (Deduction)
While the syllabus emphasizes exhaustion and counter-examples, you also need to understand the general structure of proof. This usually involves using algebra to show something is always true.
Example: Prove that the product of two odd numbers is always odd.
Step 1: Define your numbers.
Let the first odd number be \( 2n + 1 \) and the second be \( 2m + 1 \).
Step 2: Multiply them.
\( (2n + 1)(2m + 1) = 4nm + 2n + 2m + 1 \)
Step 3: Factor out a 2.
\( 2(2nm + n + m) + 1 \)
Step 4: Conclude.
Since the result is in the form \( 2(\text{integer}) + 1 \), the product must be odd.
Summary Checklist
- Proof: A logical chain of steps to reach a conclusion.
- Proof by Exhaustion: Test every single possible case (only works for small sets).
- Counter-example: Find one case where the rule fails to prove the whole statement is false.
- Key Terms: Integer (whole number), Rational (fraction), Identity (true for all values).
Final Tip: When you finish a proof, it's traditional to write Q.E.D. or draw a small square \( \square \). It stands for "Quod Erat Demonstrandum," which is just a fancy Latin way of saying, "I proved what I set out to prove!" You've got this!