Mathematical Proof - The Art of Knowing for Certain
In everyday life, we say something is “proved” when there is strong evidence for it. In mathematics, the standard is far higher. A mathematical proof is a watertight logical argument that shows a statement must be true, with absolutely no room for doubt. It is one of the most powerful ideas in all of human thought.
What Is a Proof?
A proof is a finite sequence of logical steps that begins from known truths (axioms or previously proved theorems) and reaches a conclusion through valid reasoning. Every single step must follow necessarily from what came before. One gap in the logic – however small – makes the argument invalid.
Key Vocabulary
| Term | Meaning |
|---|---|
| Axiom | A statement accepted as true without proof (the starting point) |
| Theorem | A statement that has been proved |
| Lemma | A smaller result proved in order to help prove a larger theorem |
| Corollary | A result that follows easily from a theorem |
| Conjecture | A statement believed to be true but not yet proved |
| Counterexample | A single example that disproves a general statement |
Method 1: Direct Proof
Start from the given assumptions and use logical steps to reach the conclusion directly. This is the most straightforward proof method.
Let a and b be even integers.
By definition of even: a = 2m and b = 2n for some integers m, n.
Then a + b = 2m + 2n = 2(m + n).
Since m + n is an integer, a + b is divisible by 2.
Therefore a + b is even. □
Let n be odd, so n = 2k + 1 for some integer k.
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.
This has the form 2m + 1 where m = 2k² + 2k, so n² is odd. □
Method 2: Proof by Contradiction
Assume the opposite of what you want to prove, then show this assumption leads to a logical impossibility (a contradiction). Since the assumption is false, the original statement must be true.
Assume √2 is rational. Then √2 = p/q where p and q are integers with no common factors (the fraction is in its simplest form).
Squaring: 2 = p²/q² → p² = 2q².
So p² is even, which means p must be even (since odd squared is odd). Write p = 2m.
Then (2m)² = 2q² → 4m² = 2q² → q² = 2m².
So q² is even, meaning q is even too. But now both p and q are even – contradicting our assumption that they share no common factors.
The assumption is false; therefore √2 is irrational. □
Method 3: Proof by Mathematical Induction
Used to prove statements about all natural numbers. There are two steps:
Base case: Show the statement is true for the first value (usually n = 1).
Inductive step: Assume the statement is true for n = k (the induction hypothesis), then prove it is true for n = k + 1.
If both steps hold, the statement is true for all natural numbers.
Base case (n = 1): Left side = 1. Right side = 1(2)/2 = 1. True. ✓
Inductive step: Assume 1 + 2 + ... + k = k(k+1)/2.
Add (k+1) to both sides:
1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)[k/2 + 1] = (k+1)(k+2)/2.
This is exactly the formula with n = k+1. □
By induction, the formula holds for all positive integers n.
Method 4: Proof by Counterexample
To disprove a universal statement (“this is always true”), you only need one counterexample. A single exception destroys a general claim.
Counterexample: 2 is a prime number and it is even.
The statement is false. □
The formula works for n = 0, 1, 2, ... 39 (giving primes each time – remarkably).
At n = 40: 40² + 40 + 41 = 1600 + 40 + 41 = 1681 = 41². Not prime. □
Famous Unsolved Problems
Some mathematical statements have been believed true for centuries but never proved:
Goldbach’s Conjecture (1742): every even integer greater than 2 is the sum of two primes. Verified for numbers up to 4 × 1018, but unproved.
The Riemann Hypothesis (1859): all non-trivial zeros of the Riemann zeta function have real part 1/2. One of the Millennium Prize Problems, worth $1 million for a proof.
Twin Prime Conjecture: there are infinitely many pairs of primes differing by 2 (e.g. 11 and 13). Huge progress made in 2013 but not yet fully resolved.
Key Takeaways
- A proof is a logically watertight argument; every step must follow from what came before.
- Direct proof: derive the conclusion from the assumptions.
- Proof by contradiction: assume the opposite and derive a logical impossibility.
- Induction: prove the base case, then prove the step from k to k+1.
- One counterexample is enough to disprove any universal statement.
Practice Questions
- Prove directly: the product of two odd numbers is always odd.
- Prove by contradiction: there is no largest prime number.
- Use induction to prove: 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6.
- Disprove by counterexample: “If n² is divisible by 4, then n is divisible by 4.”
- What is the difference between a conjecture and a theorem? Give one example of each.