Proof

Welcome to the World of Mathematical Proof!

In most subjects, we look for evidence to see if something is likely to be true. In Mathematics, we go one step further: we use Proof to show that something is always true, without a shadow of a doubt. Think of a proof as a legal case where you are the lawyer, using cold, hard logic to convince a jury that your statement is 100% correct.
Don't worry if this seems a bit abstract at first! We are going to break it down into four simple tools you can use to solve any "Prove that..." question in your MEI H640 exam.

1. The Building Blocks: What is a Proof?

A mathematical proof is a formal way of showing that a statement (called a conjecture) is true. It follows a very specific structure:

• Assumptions: The things we know or assume to be true at the start (e.g., "Let \(n\) be an even integer").
• Logical Steps: A chain of reasoning where each step follows naturally from the one before.
• Conclusion: The final statement that proves the original idea.

Quick Review: Key Terms
Statement: A sentence that is either true or false.
Conjecture: A mathematical statement that is thought to be true but hasn't been proven yet.
Theorem: A conjecture that has been proven true!

2. Proof by Deduction

This is the most common type of proof. You start from known facts and "deduce" the result using algebra. It’s like following a recipe—if you follow the steps correctly, you’ll always get the right result.

Example: Prove that the sum of any two even numbers is always even.

Step 1: Define your terms.
Let the first even number be \(2m\) and the second even number be \(2n\), where \(m\) and \(n\) are integers.
(Memory Aid: Any even number can be written as \(2 \times\) something!)

Step 2: Perform the operation.
Sum = \(2m + 2n\)

Step 3: Show it fits the definition.
Factor out the 2: \(Sum = 2(m + n)\)
Since \(m + n\) is an integer, \(2(m + n)\) must be an even number.

Step 4: Conclusion.
Therefore, the sum of two even numbers is always even.

Common Mistake to Avoid: Don't use specific numbers (like \(2 + 4 = 6\)) to prove a general rule. That is an illustration, not a proof. You must use letters like \(n\) and \(k\) to represent all possible numbers.

Key Takeaway: Proof by Deduction uses algebra to move directly from the start to the finish.

3. Proof by Exhaustion

This method sounds tiring, but it’s actually quite simple! Exhaustion means you test every single possibility until there are none left to check. This only works if there is a small, finite number of cases.

Analogy: If you want to prove everyone in a small room is wearing shoes, you just look at every person’s feet. Once you’ve checked everyone, the proof is "exhausted."

Example: Prove that \(n^2 + 2\) is not divisible by 4 for \(n \in \{1, 2, 3\}\).

Case 1: If \(n = 1\), \(1^2 + 2 = 3\) (Not divisible by 4).
Case 2: If \(n = 2\), \(2^2 + 2 = 6\) (Not divisible by 4).
Case 3: If \(n = 3\), \(3^2 + 2 = 11\) (Not divisible by 4).
Since we have checked all possible values of \(n\), the statement is proven.

Key Takeaway: Use Exhaustion when you can break the problem down into a few manageable cases.

4. Disproof by Counter-example

Mathematics is very strict. For a rule to be true, it must be true all the time. To disprove a conjecture, you only need to find one case where it doesn't work. This is called a counter-example.

Analogy: If someone says "All birds can fly," you just have to point to one Penguin to prove them wrong. You don't need to find every flightless bird; just one is enough!

Example: Disprove the conjecture "All prime numbers are odd."

Counter-example: The number 2 is a prime number, but it is even.
Therefore, the conjecture is false.

Key Takeaway: A single counter-example is enough to destroy a mathematical argument.

5. Proof by Contradiction

This is the "secret agent" of proofs. It feels a bit backwards! To prove something is true, you start by assuming it is false, and then show that this leads to something impossible (a contradiction).

How it works:
1. Assume the opposite of what you want to prove.
2. Use logical steps until you reach a total nonsense result (like \(1 = 0\) or saying a number is both even and odd).
3. Since logic doesn't fail, your original assumption must have been the mistake!
4. Therefore, the original statement must be true.

The "Famous Two" Contradictions (Required for MEI H640)

A. Prove that \(\sqrt{2}\) is irrational

1. The Assumption: Assume \(\sqrt{2}\) is rational. This means it can be written as a fraction \(\frac{a}{b}\) in its simplest form (where \(a\) and \(b\) have no common factors).
2. The Algebra: \(\sqrt{2} = \frac{a}{b} \implies 2 = \frac{a^2}{b^2} \implies 2b^2 = a^2\).
3. The Deduction: This means \(a^2\) is even, so \(a\) must be even. Let \(a = 2k\).
4. More Algebra: Substitute \(a = 2k\) back in: \(2b^2 = (2k)^2 \implies 2b^2 = 4k^2 \implies b^2 = 2k^2\).
5. The Conflict: This means \(b^2\) is even, so \(b\) must be even.
6. The Contradiction: We said \(\frac{a}{b}\) was in simplest form, but we just showed both \(a\) and \(b\) are even (so they could both be divided by 2!).
7. Conclusion: Our assumption was wrong. \(\sqrt{2}\) must be irrational.

B. Prove there are infinitely many prime numbers

1. The Assumption: Assume there is a finite list of primes: \(p_1, p_2, ..., p_n\).
2. The Logic: Imagine a new number \(N = (p_1 \times p_2 \times ... \times p_n) + 1\).
3. The Contradiction: If you divide \(N\) by any of our "known" primes, you will always get a remainder of 1. This means either \(N\) itself is prime, or it has a prime factor that isn't on our list.
4. Conclusion: There is always another prime. Therefore, the number of primes is infinite.

Did you know? This proof for primes was first written by Euclid over 2,000 years ago! It is still considered one of the most beautiful proofs in history.

Key Takeaway: Contradiction proves a statement by showing that the opposite is impossible.

Summary Checklist for Students

• Can I define an even number as \(2n\) and an odd number as \(2n+1\)?
• Do I know when to use Exhaustion (small number of cases) vs Deduction (general cases)?
• Am I looking for that one counter-example to disprove a theory?
• Can I replicate the step-by-step logic for the irrationality of \(\sqrt{2}\)?
• Do I remember to finish my proofs with a clear concluding statement?

Keep practicing! Proof is a skill that gets much easier the more "logical paths" you see. You've got this!