Proof
Proof
Mathematical proof is the process of establishing that a statement is true using logical reasoning. At A-Level, you must be able to construct proofs using several different methods and understand the logical structure behind them.
Types of Proof
Proof by Deduction
Start from known facts, definitions or assumptions and use logical steps to arrive at the conclusion. This is the most common type of proof.
Worked Example: Prove that the sum of any two consecutive integers is odd.
Let the two consecutive integers be n and n + 1, where n is an integer.
Their sum = n + (n + 1) = 2n + 1.
Since 2n is even (it is a multiple of 2), 2n + 1 is odd.
Therefore the sum of any two consecutive integers is odd. QED.
Worked Example: Prove that (3n + 1)² - (3n - 1)² is a multiple of 12 for all positive integers n.
(3n + 1)² - (3n - 1)² = (9n² + 6n + 1) - (9n² - 6n + 1)
= 12n
Since n is a positive integer, 12n is a multiple of 12. QED.
Proof by Exhaustion
Check every possible case. This only works when there are a finite number of cases to verify.
Worked Example: Prove that n² + n + 1 is odd for all integers n.
Case 1: n is even, so n = 2k. Then n² + n + 1 = 4k² + 2k + 1 = 2(2k² + k) + 1, which is odd.
Case 2: n is odd, so n = 2k + 1. Then n² + n + 1 = (2k+1)² + (2k+1) + 1 = 4k² + 4k + 1 + 2k + 1 + 1 = 4k² + 6k + 3 = 2(2k² + 3k + 1) + 1, which is odd.
All integers are either even or odd, so the result holds for all integers. QED.
Proof by Contradiction
Assume the opposite of what you want to prove, then show this leads to a logical contradiction. This forces the original statement to be true.
Worked Example: Prove that √2 is irrational.
Assume √2 is rational. Then √2 = a/b where a and b are integers with no common factors (the fraction is in lowest terms).
Squaring: 2 = a²/b², so a² = 2b².
This means a² is even, so a must be even (since odd² is odd). Write a = 2k.
Then (2k)² = 2b², so 4k² = 2b², giving b² = 2k².
This means b² is even, so b must be even.
But if both a and b are even, they share a common factor of 2. This contradicts our assumption that a/b was in lowest terms.
Therefore √2 is irrational. QED.
Worked Example: Prove that there are infinitely many prime numbers.
Assume there are finitely many primes: p₁, p₂, ..., pₙ.
Consider N = p₁ × p₂ × ... × pₙ + 1.
N is not divisible by any of p₁, ..., pₙ (division leaves remainder 1).
So either N is prime (a prime not in our list) or N has a prime factor not in our list.
Either way, there exists a prime not in our supposed complete list. Contradiction.
Therefore there are infinitely many primes. QED.
Disproof by Counter-Example
To disprove a statement, you only need one counter-example — a specific case where the statement fails.
Worked Example: Disprove: "n² + n + 41 is prime for all positive integers n."
Test n = 41: 41² + 41 + 41 = 41(41 + 1 + 1) = 41 × 43 = 1763.
Since 1763 = 41 × 43, it is not prime. The statement is false.
Key Logical Terminology
| Term | Meaning |
|---|---|
| Conjecture | A statement believed to be true but not yet proven |
| Theorem | A statement that has been proven true |
| Corollary | A result that follows directly from a theorem |
| Converse | The reverse implication (if P→Q, then Q→P is the converse) |
| Contrapositive | If P→Q, then not-Q→not-P (always has the same truth value) |
| Necessary | A condition that must hold ("if P then Q" means Q is necessary for P) |
| Sufficient | A condition that guarantees the result (P is sufficient for Q) |
Structure of a Proof
A well-written proof should:
1. State what you are proving (or what you are assuming, for contradiction)
2. Define variables ("let n be an integer")
3. Present logical steps, each following from the previous
4. Arrive at a clear conclusion (restate what has been shown)
5. End with "QED" or "as required"
Exam Tips
- In proof by deduction, always start with "let n be..." and define your variable type (integer, positive integer, etc.).
- For proof by contradiction, clearly state your assumption at the start and clearly identify the contradiction at the end.
- Exhaustion proofs must cover all cases — make sure none are missed.
- A counter-example must be specific — show the calculation, do not just state the number.
- The mark scheme typically requires correct logical connectives ("therefore", "so", "since", "which contradicts..."). Vague reasoning loses marks.