Why proofs matter
In science, evidence supports theories. In mathematics, a proof settles a question forever. Once the Pythagorean theorem was proven, it has stayed true for over 2,000 years.
What a proof needs
- Clear statements of what’s given and what’s to be proven
- Definitions, axioms and previously proven theorems
- Logical steps, each justified
- A conclusion, often marked ∎ or QED
Direct proof
Start from known facts and reason step by step to the conclusion. This is a direct proof.
Prove: The sum of two even numbers is even.
- Let the numbers be 2a and 2b (a, b integers).
- 2a + 2b = 2(a + b).
- Since a + b is an integer, the sum is even. ∎
Prove: The square of an odd number is odd.
- Let n = 2k + 1.
- n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ∎
Proof by contradiction
Assume the opposite of what you want to prove, then show this leads to something impossible. This is proof by contradiction.
Prove: √2 is irrational.
- Suppose √2 = a/b, a fraction in lowest terms.
- Then 2 = a²/b² → a² = 2b², so a² is even, so a is even. Write a = 2c.
- Then 4c² = 2b² → b² = 2c², so b is even too.
- But then a and b share the factor 2, contradicting "lowest terms". ∎
Prove: There are infinitely many primes (Euclid).
Suppose there are finitely many primes p₁, …, pₙ. Let N = p₁p₂…pₙ + 1. N leaves remainder 1 when divided by every pᵢ, so N has a prime factor not on the list. Contradiction. ∎
Proof by induction
Proof by induction proves statements for all whole numbers n ≥ 1, like a line of dominoes:
- Base case: show it’s true for n = 1.
- Inductive step: assume it’s true for n = k; prove it’s true for n = k + 1.
Prove: 1 + 2 + … + n = n(n + 1)/2
- Base: n = 1 → 1 = 1(2)/2 ✓
- Step: Assume 1 + … + k = k(k + 1)/2. Then 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2 ✓ ∎
Disproof by counterexample
To show a general statement is false, one counterexample is enough.
"n² + n + 41 is always prime" fails at n = 40: 40² + 40 + 41 = 1,681 = 41².
Proof vs evidence
Checking 1,000 cases isn’t a proof. Some famous conjectures held for millions of cases before failing. Only a proof covers every case.
Worked examples
Example 1: Which method suits "√3 is irrational"? Contradiction.
Example 2: Which method suits "2ⁿ > n for all n ≥ 1"? Induction.
Example 3: Disprove "all odd numbers are prime." 9.
Common mistakes
- Using examples as proof.
- Assuming what you’re trying to prove.
- Skipping the base case in induction.
Try it yourself
- Prove: the product of two odd numbers is odd.
- Name the method: assume the opposite and reach an impossibility.
- Give a counterexample: "every prime number is odd."
- In induction, what must be shown besides the base case?
Answers: 1) (2a + 1)(2b + 1) = 2(2ab + a + b) + 1, which is odd. 2) proof by contradiction 3) 2 4) If true for k, then true for k + 1.
Quick recap
- A proof shows a statement is always true.
- Methods: direct proof, proof by contradiction, proof by induction.
- One counterexample disproves a general claim.