Welcome to the World of Mathematical Proof!
Ever had an argument where you knew you were 100% right, but you couldn't quite explain why? In Mathematics, a proof is the ultimate way of winning that argument. It is a logical "bridge" that connects things we already know to a new conclusion that must be true.
In this chapter, we will learn how to move beyond "it looks like it works" to "I have proven it always works." This is the foundation of all high-level mathematics!
1. The Building Blocks: What is a Proof?
A mathematical proof is a series of logical steps that starts from assumptions (things we know are true) and leads to a conclusion. Once something is proven, it becomes a theorem.
Don't worry if this seems tricky at first! Proofs are just like following a recipe. If you use the right ingredients and follow the steps, you’ll get the right result every time.
Prerequisite Knowledge: Even and Odd Numbers
To write proofs about numbers, we need a "math way" to write "even" and "odd":
- Even Numbers: Can always be written as \( 2n \), where \( n \) is any integer (\( \dots, -2, -1, 0, 1, 2, \dots \)).
- Odd Numbers: Are always one more than an even number, so we write them as \( 2n + 1 \).
- Integers: We often use the symbol \( \mathbb{Z} \) to represent the set of all whole numbers.
Quick Review: If \( n \) is an integer, \( 2n \) is always even and \( 2n + 1 \) is always odd.
2. Proof by Deduction
Proof by deduction (also called direct proof) is the most common method. You start with known facts and use algebra or logic to reach your goal. Think of it like a detective building a case using clues.
Step-by-Step Example
Prove that the sum of any two even numbers is always even.
Step 1: Define your numbers using algebra.
Let our first even number be \( 2n \) and our second even number be \( 2m \), where \( n \) and \( m \) are integers.
Step 2: Perform the operation requested (Summing).
Sum = \( 2n + 2m \)
Step 3: Factorize to show the property.
We can factor out a 2: \( 2(n + m) \)
Step 4: State your conclusion.
Since \( n + m \) is an integer, \( 2(n + m) \) fits the definition of an even number. Therefore, the sum of two even numbers is always even. Proof complete!
Common Mistake to Avoid
When proving something for any two numbers, don't use the same letter! If you use \( 2n \) and \( 2n \), you are only proving it for when the numbers are the same. Use \( 2n \) and \( 2m \) to keep them general.
Key Takeaway: Deduction uses algebra to show that a statement is true for every possible value.
3. Proof by Exhaustion
Sometimes, it is impossible to write a general algebraic proof. If there are only a few cases to check, you can just check every single one! This is called Proof by Exhaustion.
Analogy: If you want to prove that every light switch in your living room works, you don't need a complex electrical diagram—you can just walk around and flip every switch.
Example
Prove that \( n^2 + 2 \) is a prime number for all integers \( n \) such that \( 1 \leq n \leq 3 \).
In this case, the "universe" of numbers we care about is very small: \( n \) can only be 1, 2, or 3.
- Case 1: When \( n = 1 \), \( 1^2 + 2 = 3 \). (3 is prime!)
- Case 2: When \( n = 2 \), \( 2^2 + 2 = 6 \). Wait! 6 is not prime.
(Self-Correction: If one case fails, the statement is false. If the statement was "Prove \( n^2 + 1 \) is prime for \( 1 \leq n \leq 3 \)", we would check \( n=1, 2, 3 \) and find they all work.)
When to use it?
- When the question gives you a specific, small range of numbers.
- When a property can be split into "Even" and "Odd" cases (and you test both).
Did you know? Computers are great at proof by exhaustion! In 1976, the "Four Color Map Theorem" was proven by a computer checking nearly 2,000 different cases that humans couldn't do by hand.
Key Takeaway: Exhaustion means checking every individual case to see if the rule holds true for all of them.
4. Disproof by Counter-example
In math, a conjecture is a statement that people think is true but hasn't been proven yet. To disprove a conjecture, you don't need a long argument. You only need one single example where it doesn't work.
This single "failure" is called a counter-example.
Analogy: If someone says, "All birds can fly," you can disprove them just by pointing at one penguin. You don't need to talk about ostriches or emus—one penguin is enough to make the statement false.
Example
Disprove the conjecture: "\( n^2 - n + 11 \) is a prime number for all positive integers \( n \)."
Let's try some values:
- If \( n = 1 \): \( 1^2 - 1 + 11 = 11 \) (Prime)
- If \( n = 2 \): \( 2^2 - 2 + 11 = 13 \) (Prime)
- If \( n = 11 \): \( 11^2 - 11 + 11 = 11^2 = 121 \).
Since \( 121 \) is \( 11 \times 11 \), it is not prime. Therefore, \( n = 11 \) is a counter-example, and the conjecture is disproved.
Memory Aid: The "Party Pooper" Method
Think of Disproof by Counter-example as being a "Party Pooper." Everyone is celebrating a new rule, and you walk in with one specific reason why it’s wrong!
Key Takeaway: To kill a bad math rule, you only need one example where it fails.
Summary Checklist for the Exam
- Deduction: Use algebra (\( 2n, 2n+1 \)) to show it always works.
- Exhaustion: List and test every single case if the group is small.
- Counter-example: Find just one number that breaks the rule to show the rule is false.
- Language: Always finish by stating your conclusion clearly (e.g., "Hence, the statement is true by deduction").
Final Tip: If a question asks you to "Prove" something, it’s probably true. If it asks you to "Determine if it is true," start by looking for a counter-example!