Mathematical Proofs: A Comprehensive Guide
Table of Contents
1. Introduction to Mathematical Proofs
What is a Mathematical Proof?
A mathematical proof is a rigorous logical argument that establishes the truth of a mathematical statement. It's a sequence of statements that follow logically from a set of axioms (basic assumptions) or previously proven theorems, leading to a conclusion.
Mathematical proofs are the foundation of mathematical reasoning. They provide certainty beyond empirical evidence or examples. While testing examples can suggest a statement is true, only a proof can establish it with absolute certainty.
Key Elements of a Good Proof
- Clarity: Each step should be clear and understandable.
- Completeness: No logical gaps should exist in the reasoning.
- Precision: Terminology and notation must be precise.
- Rigor: All claims must be justified by axioms, definitions, or theorems.
- Structure: The proof should follow a logical flow.
Common Proof Techniques
Here are the major proof techniques we'll explore in detail:
| Technique | Core Approach | Best Used For |
|---|---|---|
| Direct Proof | Assume P is true and show Q is true | Straightforward implications |
| Proof by Contradiction | Assume statement is false and derive a contradiction | When direct approach is difficult |
| Proof by Contrapositive | Prove "not Q implies not P" instead of "P implies Q" | When the contrapositive is easier to work with |
| Mathematical Induction | Prove base case and inductive step | Statements involving natural numbers |
| Proof by Cases | Break proof into exhaustive cases and prove each | When different scenarios need different approaches |
| Existence Proofs | Show there exists at least one instance | Demonstrating existence of mathematical objects |
| Uniqueness Proofs | Show there exists exactly one instance | Demonstrating uniqueness of solutions |
2. Direct Proof
Definition
A direct proof establishes the truth of a statement by starting with known facts or assumptions and applying logical steps to arrive at the conclusion directly. For an implication "if P, then Q," we assume P and demonstrate Q.
Example 1: Proving a Sum of Even Numbers is Even
Theorem: The sum of two even integers is even.
Proof:
Let x and y be even integers. By definition of even numbers, there exist integers m and n such that:
x = 2m and y = 2n
Now, consider the sum x + y:
x + y = 2m + 2n = 2(m + n)
Since m + n is an integer, we can say that x + y = 2(m + n) is even by definition.
Therefore, the sum of two even integers is even. ■
Example 2: Proving a Property of Divisibility
Theorem: If n is an integer and n² is even, then n is even.
Proof:
We'll use a direct proof. Assume n is not even. Then n is odd.
If n is odd, then n = 2k + 1 for some integer k.
Therefore, n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
Since 2k² + 2k is an integer, n² = 2(2k² + 2k) + 1 is odd.
But this contradicts our initial assumption that n² is even.
Therefore, n must be even. ■
Step-by-Step Approach to Direct Proofs
Practice Problem
Prove that the product of two odd integers is odd.
Proof:
Let a and b be odd integers. By definition, there exist integers m and n such that:
a = 2m + 1 and b = 2n + 1
Now consider the product a × b:
a × b = (2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1
Since 2mn + m + n is an integer, a × b = 2(2mn + m + n) + 1 is odd by definition.
Therefore, the product of two odd integers is odd. ■
3. Proof by Contradiction
Definition
A proof by contradiction (also called indirect proof or reductio ad absurdum) establishes the truth of a statement by assuming its negation is true and showing this leads to a logical contradiction. This demonstrates the original statement must be true.
Example 1: Irrationality of √2
Theorem: √2 is irrational.
Proof:
Assume, for contradiction, that √2 is rational. Then √2 = a/b for some integers a and b where b ≠ 0 and a and b have no common factors (i.e., in lowest terms).
Squaring both sides: 2 = a²/b²
Multiplying both sides by b²: 2b² = a²
This means a² is even, which implies a is even (as proven earlier).
So a = 2k for some integer k. Substituting: 2b² = (2k)² = 4k²
Dividing both sides by 2: b² = 2k²
This means b² is even, which implies b is even.
But this contradicts our assumption that a and b have no common factors (both would be divisible by 2).
Therefore, our initial assumption is false, and √2 must be irrational. ■
Example 2: Infinitude of Primes
Theorem: There are infinitely many prime numbers.
Proof:
Assume, for contradiction, that there are only finitely many primes, and we can list them all: p₁, p₂, p₃, ..., pₙ.
Consider the number Q = p₁ × p₂ × p₃ × ... × pₙ + 1.
Q is either prime or not prime.
If Q is prime, then Q is a prime number that is not in our list (since Q > pᵢ for all i), contradicting our assumption.
If Q is not prime, then Q must be divisible by some prime number p. This prime p must be in our list, so p = pᵢ for some i.
Since pᵢ divides Q, and pᵢ divides p₁ × p₂ × p₃ × ... × pₙ, pᵢ must also divide their difference:
Q - (p₁ × p₂ × p₃ × ... × pₙ) = 1
This implies pᵢ divides 1, which is impossible for any prime number.
Therefore, our assumption is false, and there must be infinitely many primes. ■
Step-by-Step Approach to Contradiction Proofs
Practice Problem
Prove that there is no largest integer.
Proof:
Assume, for contradiction, that there is a largest integer, call it N.
Consider the number N + 1.
Since N + 1 > N, and N is the largest integer, N + 1 cannot be an integer.
But N + 1 is clearly an integer because the sum of an integer and 1 is always an integer.
This is a contradiction.
Therefore, our assumption is false, and there is no largest integer. ■
4. Proof by Contrapositive
Definition
A proof by contrapositive establishes an implication "if P, then Q" by proving its contrapositive "if not Q, then not P". Logically, an implication and its contrapositive are equivalent, but sometimes the contrapositive is easier to prove directly.
Logical Equivalence
The statement "P → Q" is logically equivalent to "¬Q → ¬P"
Example 1: Divisibility Property
Theorem: If n² is even, then n is even.
Proof (by contrapositive):
We'll prove the contrapositive: "If n is not even, then n² is not even."
If n is not even, then n is odd, so n = 2k + 1 for some integer k.
Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
Since 2k² + 2k is an integer, n² = 2(2k² + 2k) + 1 is odd.
Therefore, n² is not even.
This proves the contrapositive, so the original statement is true. ■
Example 2: A Property of Real Numbers
Theorem: If x² < 9, then -3 < x < 3.
Proof (by contrapositive):
We'll prove: "If x ≤ -3 or x ≥ 3, then x² ≥ 9."
Consider two cases:
Case 1: If x ≤ -3, then x² ≥ (-3)² = 9
Case 2: If x ≥ 3, then x² ≥ 3² = 9
In both cases, x² ≥ 9, which is the negation of x² < 9.
This proves the contrapositive, so the original statement is true. ■
Step-by-Step Approach to Contrapositive Proofs
Practice Problem
Prove that if x² + y² = 25 and xy = 12, then x + y ≠ 0.
Proof (by contrapositive):
We'll prove: "If x + y = 0, then x² + y² ≠ 25 or xy ≠ 12."
If x + y = 0, then y = -x.
Substituting this into xy = 12:
x(-x) = 12
-x² = 12
x² = -12
Since x² must be non-negative for any real x, the equation x² = -12 has no solution.
Therefore, if x + y = 0, then xy ≠ 12.
This proves the contrapositive, so the original statement is true. ■
5. Mathematical Induction
Definition
Mathematical induction is a proof technique used to prove that a statement P(n) is true for all natural numbers n, or starting from some fixed number. It involves two steps:
- Base Case: Prove P(1) is true (or P(k) for some starting value k).
- Inductive Step: Prove that if P(k) is true, then P(k+1) is also true for any arbitrary k.
Example 1: Sum of First n Natural Numbers
Theorem: For all n ≥ 1, the sum 1 + 2 + 3 + ... + n = n(n+1)/2.
Proof (by induction):
Base Case: For n = 1, we have 1 = 1(1+1)/2 = 1, which is true.
Inductive Hypothesis: Assume the formula is true for n = k, that is:
1 + 2 + 3 + ... + k = k(k+1)/2
Inductive Step: We need to prove the formula is true for n = k+1, that is:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2
Starting from the left side:
1 + 2 + 3 + ... + k + (k+1) = [1 + 2 + 3 + ... + k] + (k+1)
Using our inductive hypothesis:
= k(k+1)/2 + (k+1)
= (k+1)[k/2 + 1]
= (k+1)[k/2 + 2/2]
= (k+1)[(k+2)/2]
= (k+1)(k+2)/2
This is exactly what we needed to prove.
By the principle of mathematical induction, the statement is true for all natural numbers n ≥ 1. ■
Example 2: Divisibility Property
Theorem: For all n ≥ 0, 5ⁿ - 1 is divisible by 4.
Proof (by induction):
Base Case: For n = 0, we have 5⁰ - 1 = 1 - 1 = 0, which is divisible by 4.
Inductive Hypothesis: Assume the statement is true for n = k, that is:
5ᵏ - 1 is divisible by 4, so 5ᵏ - 1 = 4m for some integer m.
Inductive Step: We need to prove the statement is true for n = k+1, that is:
5^(k+1) - 1 is divisible by 4.
5^(k+1) - 1 = 5 × 5ᵏ - 1
= 5 × 5ᵏ - 5 + 5 - 1
= 5(5ᵏ - 1) + 4
By our inductive hypothesis, 5ᵏ - 1 = 4m, so:
5^(k+1) - 1 = 5(4m) + 4 = 20m + 4 = 4(5m + 1)
Since 5m + 1 is an integer, 5^(k+1) - 1 is divisible by 4.
By the principle of mathematical induction, the statement is true for all n ≥ 0. ■
Step-by-Step Approach to Induction Proofs
Variants of Induction
- Strong Induction: Assume P(1), P(2), ..., P(k) to prove P(k+1), not just P(k).
- Complete Induction: Prove P(n) by assuming it's true for all values less than n.
- Structural Induction: Used for recursive structures like trees, proving properties hold for all structures.
Practice Problem
Prove that for all natural numbers n, 2ⁿ > n.
Proof (by induction):
Base Case: For n = 1, we have 2¹ = 2 > 1, which is true.
Inductive Hypothesis: Assume the inequality is true for n = k, that is, 2ᵏ > k.
Inductive Step: We need to prove the inequality is true for n = k+1, that is, 2^(k+1) > k+1.
Starting with our inductive hypothesis: 2ᵏ > k
Multiply both sides by 2: 2 × 2ᵏ > 2k
This gives us: 2^(k+1) > 2k
Since k is a positive integer, k ≥ 1, so k+1 ≤ 2k
Therefore: 2^(k+1) > 2k ≥ k+1
This means 2^(k+1) > k+1, which is what we needed to prove.
By the principle of mathematical induction, 2ⁿ > n for all natural numbers n. ■
6. Proof by Cases
Definition
A proof by cases establishes a statement by breaking it down into an exhaustive set of mutually exclusive cases and proving the statement for each case separately. The cases must cover all possibilities for the proof to be complete.
Example 1: Absolute Value Property
Theorem: For any real number x, |x| + |x+1| ≥ 1.
Proof (by cases):
We'll divide this into three cases based on the possible values of x.
Case 1: x ≤ -1
When x ≤ -1, we have |x| = -x and |x+1| = -(x+1) = -x-1
So |x| + |x+1| = -x + (-x-1) = -2x-1
Since x ≤ -1, we have -x ≥ 1, so -2x ≥ 2
Therefore, |x| + |x+1| = -2x-1 ≥ 2-1 = 1
Case 2: -1 < x < 0
When -1 < x < 0, we have |x| = -x and |x+1| = x+1
So |x| + |x+1| = -x + (x+1) = 1
Therefore, |x| + |x+1| = 1 ≥ 1
Case 3: x ≥ 0
When x ≥ 0, we have |x| = x and |x+1| = x+1
So |x| + |x+1| = x + (x+1) = 2x+1
Since x ≥ 0, we have 2x ≥ 0
Therefore, |x| + |x+1| = 2x+1 ≥ 0+1 = 1
In all three cases, we've shown that |x| + |x+1| ≥ 1.
Therefore, for any real number x, |x| + |x+1| ≥ 1. ■
Example 2: Parity of (n² - n)
Theorem: For any integer n, the expression n² - n is always even.
Proof (by cases):
We'll consider two cases based on the parity of n.
Case 1: n is even
If n is even, then n = 2k for some integer k.
n² - n = (2k)² - 2k = 4k² - 2k = 2(2k² - k)
Since 2k² - k is an integer, n² - n is even.
Case 2: n is odd
If n is odd, then n = 2m + 1 for some integer m.
n² - n = (2m + 1)² - (2m + 1) = 4m² + 4m + 1 - 2m - 1 = 4m² + 2m = 2(2m² + m)
Since 2m² + m is an integer, n² - n is even.
In both cases, n² - n is even.
Therefore, for any integer n, the expression n² - n is always even. ■
Step-by-Step Approach to Proofs by Cases
Practice Problem
Prove that |x - y| = max(x, y) - min(x, y) for all real numbers x and y.
Proof (by cases):
We'll consider two cases based on the relative values of x and y.
Case 1: x ≥ y
When x ≥ y, we have max(x, y) = x and min(x, y) = y
Also, |x - y| = x - y since x - y ≥ 0
Therefore, |x - y| = x - y = max(x, y) - min(x, y)
Case 2: x < y
When x < y, we have max(x, y) = y and min(x, y) = x
Also, |x - y| = -(x - y) = y - x since x - y < 0
Therefore, |x - y| = y - x = max(x, y) - min(x, y)
In both cases, we've shown that |x - y| = max(x, y) - min(x, y).
Therefore, for all real numbers x and y, |x - y| = max(x, y) - min(x, y). ■
7. Existence Proofs
Definition
An existence proof demonstrates that a mathematical object with certain properties exists. There are two main approaches:
- Constructive proof: Explicitly construct an object with the required properties.
- Non-constructive proof: Prove that such an object must exist without explicitly constructing it.
Example 1: Constructive Existence Proof
Theorem: There exists an irrational number x such that x is irrational.
Proof (constructive):
We know that √2 is irrational (as proven earlier).
Consider x = √2^(√2).
There are two possibilities:
1. If x is irrational, then we have found our irrational number x such that x^x is irrational (since x itself is irrational).
2. If x is rational, then √2^(√2) is rational. Let's call this rational number r.
Consider r^r = (√2^(√2))^r = √2^(√2·r).
Since √2 is irrational and √2·r is irrational (as the product of an irrational and a non-zero rational), r^r is irrational.
In this case, r would be our rational number such that r^r is irrational.
Therefore, either x = √2^(√2) or x = r satisfies our requirement. ■
Example 2: Non-Constructive Existence Proof
Theorem: There exist irrational numbers a and b such that a^b is rational.
Proof (non-constructive):
Consider √2^(√2).
Either this number is rational or irrational.
Case 1: If √2^(√2) is rational, then with a = √2 and b = √2, we have a^b is rational, and both a and b are irrational.
Case 2: If √2^(√2) is irrational, let's call it c. Consider c^(√2).
c^(√2) = (√2^(√2))^(√2) = √2^(√2·√2) = √2^2 = 2, which is rational.
So with a = c = √2^(√2) and b = √2, we have a^b is rational, and both a and b are irrational.
Therefore, in either case, there exist irrational numbers a and b such that a^b is rational. ■
Step-by-Step Approach to Existence Proofs
Practice Problem
Prove that there exists a perfect square that is also a sum of two perfect squares.
Proof (constructive):
We need to find numbers a, b, and c such that a² = b² + c², where a, b, and c are integers.
Consider a = 5, b = 4, and c = 3.
Then a² = 5² = 25
And b² + c² = 4² + 3² = 16 + 9 = 25 = a²
Therefore, 25 is a perfect square that is also a sum of two perfect squares. ■
8. Uniqueness Proofs
Definition
A uniqueness proof demonstrates that there is exactly one object with certain properties. Typically, this involves two steps:
- Existence: Show that at least one object with the given properties exists.
- Uniqueness: Show that there cannot be more than one such object.
Example 1: Unique Multiplicative Identity
Theorem: There is a unique real number e such that e · x = x for all real numbers x.
Proof:
Existence: The number 1 satisfies the property since 1 · x = x for all real numbers x.
Uniqueness: Suppose there are two distinct real numbers e₁ and e₂ both satisfying the given property.
Then e₁ · x = x and e₂ · x = x for all real numbers x.
In particular, e₁ · e₂ = e₂ (using x = e₂)
Also, e₂ · e₁ = e₁ (using x = e₁)
By commutativity of multiplication, e₁ · e₂ = e₂ · e₁, so e₂ = e₁.
This contradicts our assumption that e₁ and e₂ are distinct.
Therefore, there is a unique real number, namely 1, that satisfies the given property. ■
Example 2: Unique Solution to an Equation
Theorem: The equation x² - 6x + 8 = 0 has exactly one solution that is a multiple of 4.
Proof:
Existence: We can factor the equation as (x - 2)(x - 4) = 0, which gives us solutions x = 2 and x = 4.
Of these, x = 4 is a multiple of 4.
Uniqueness: Let's suppose there is another solution x = 4k where k is an integer and k ≠ 1.
Substituting into the original equation:
(4k)² - 6(4k) + 8 = 0
16k² - 24k + 8 = 0
Dividing by 8: 2k² - 3k + 1 = 0
Using the quadratic formula: k = (3 ± √(9 - 8))/4 = (3 ± 1)/4
So k = 1 or k = 1/2
Since k must be an integer and k ≠ 1, the only possibility is k = 1/2, which is not an integer.
Therefore, x = 4 is the unique solution to the equation that is a multiple of 4. ■
Step-by-Step Approach to Uniqueness Proofs
Practice Problem
Prove that there is exactly one real number x such that x² + x = 2.
Proof:
Existence: We solve the equation x² + x = 2.
x² + x - 2 = 0
Using the quadratic formula: x = (-1 ± √(1 + 8))/2 = (-1 ± 3)/2
So x = 1 or x = -2
Checking these solutions:
For x = 1: 1² + 1 = 1 + 1 = 2 ✓
For x = -2: (-2)² + (-2) = 4 - 2 = 2 ✓
Both solutions satisfy the equation, so there are actually two real numbers that satisfy x² + x = 2.
The statement is false! There are exactly two real numbers, not one, that satisfy the equation. ■
9. Comprehensive Quiz
10. Practice Problems
Problem 1: Direct Proof
Prove that the sum of three consecutive integers is divisible by 3.
Proof:
Let the three consecutive integers be n, n+1, and n+2 for some integer n.
The sum of these integers is n + (n+1) + (n+2) = 3n + 3 = 3(n+1).
Since n+1 is an integer, 3(n+1) is divisible by 3.
Therefore, the sum of three consecutive integers is divisible by 3. ■
Problem 2: Proof by Contradiction
Prove that there are infinitely many integers n such that n² - n + 41 is not prime.
Proof (by contradiction):
Let's assume the contrary: that there are only finitely many integers n such that n² - n + 41 is not prime.
Consider n = 41. Then n² - n + 41 = 41² - 41 + 41 = 41² = 41 × 41.
This is clearly not prime as it equals 41 × 41.
Consider n = 40 + 41k for any integer k. Then:
n² - n + 41 = (40 + 41k)² - (40 + 41k) + 41
= 1600 + 3280k + 1681k² - 40 - 41k + 41
= 1601 + 3239k + 1681k²
When k = 1: n = 81, n² - n + 41 = 1601 + 3239 + 1681 = 6521 = 41 × 159
We can continue this pattern to find infinitely many values of n where n² - n + 41 is divisible by 41 and therefore not prime.
This contradicts our assumption, so there must be infinitely many integers n such that n² - n + 41 is not prime. ■
Problem 3: Proof by Contrapositive
Prove that if n³ - 2n is odd, then n is odd.
Proof (by contrapositive):
We'll prove: "If n is even, then n³ - 2n is even."
If n is even, then n = 2k for some integer k.
n³ - 2n = (2k)³ - 2(2k) = 8k³ - 4k = 4k(2k² - 1)
Since 4k(2k² - 1) is divisible by 4, it is even.
Therefore, if n is even, then n³ - 2n is even.
By contrapositive, if n³ - 2n is odd, then n is odd. ■
Problem 4: Mathematical Induction
Prove that for all n ≥ 1, 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6.
Proof (by induction):
Base Case: For n = 1, we have 1² = 1, and n(n+1)(2n+1)/6 = 1(1+1)(2·1+1)/6 = 1·2·3/6 = 1, which is true.
Inductive Hypothesis: Assume the formula is true for n = k, that is:
1² + 2² + 3² + ... + k² = k(k+1)(2k+1)/6
Inductive Step: We need to prove the formula is true for n = k+1, that is:
1² + 2² + 3² + ... + k² + (k+1)² = (k+1)(k+2)(2k+3)/6
Starting with the left side:
1² + 2² + 3² + ... + k² + (k+1)² = [1² + 2² + 3² + ... + k²] + (k+1)²
Using our inductive hypothesis:
= k(k+1)(2k+1)/6 + (k+1)²
= k(k+1)(2k+1)/6 + (k+1)²·6/6
= (k+1)[k(2k+1) + 6(k+1)]/6
= (k+1)[2k² + k + 6k + 6]/6
= (k+1)[2k² + 7k + 6]/6
= (k+1)[(2k+3)(k+2)]/6
= (k+1)(k+2)(2k+3)/6
This is exactly what we needed to prove.
By the principle of mathematical induction, the formula is true for all natural numbers n ≥ 1. ■
Problem 5: Proof by Cases
Prove that for any two real numbers a and b, max(a,b) + min(a,b) = a + b.
Proof (by cases):
We'll consider two cases based on the relative values of a and b.
Case 1: a ≥ b
When a ≥ b, we have max(a,b) = a and min(a,b) = b
Therefore, max(a,b) + min(a,b) = a + b
Case 2: a < b
When a < b, we have max(a,b) = b and min(a,b) = a
Therefore, max(a,b) + min(a,b) = b + a = a + b
In both cases, we've shown that max(a,b) + min(a,b) = a + b.
Therefore, for any two real numbers a and b, max(a,b) + min(a,b) = a + b. ■