When faced with a statement to prove, the difficulty is often not the mathematics itself but choosing where to start. There is a small catalogue of strategies that covers the vast majority of cases. Knowing them helps not only with writing proofs, but also with reasoning about whether an algorithm is correct or understanding why an idea does not work.
Direct proof
You start from the hypotheses and reach the conclusion through a chain of steps. It is the simplest strategy and worth trying first.
Statement: the sum of two odd numbers is even.
Proof: let a and b be odd. By definition a = 2h + 1 and b = 2k + 1 for some integers h and k. Then a + b = 2h + 2k + 2 = 2(h + k + 1), which is a multiple of 2, hence even.
The trick in a direct proof is almost always the same: translate the words into definitions. "Odd" becomes "2k + 1", "divisible by 3" becomes "3m", and from then on it is just algebra.
Proof by contrapositive
Instead of p → q, you prove ¬q → ¬p, which is equivalent. It pays off when the negation of the conclusion gives more information than the conclusion itself. Classic example: "if n² is even, then n is even" is proved by showing that if n is odd, n² is odd too.
Proof by contradiction
You assume the statement is false and arrive at a contradiction. Since a contradiction cannot be true, the absurd assumption must be rejected and the statement is true.
Statement: √2 is not a rational number.
Proof: suppose, for contradiction, that √2 = a/b, with a and b integers and the fraction in lowest terms. Then 2 = a²/b², so a² = 2b². Hence a² is even, and so a is even: a = 2c. Substituting, 4c² = 2b², so b² = 2c², and b is even too. But then a and b share the factor 2, contradicting the assumption that the fraction was in lowest terms. Contradiction.
A second famous example, attributed to Euclid: there are infinitely many primes. Suppose there are finitely many, p₁, …, pₙ. Consider N = p₁ · p₂ · … · pₙ + 1. Divided by any pᵢ it leaves remainder 1, so none of the listed primes divides it. But N > 1 has at least one prime factor, which is therefore not on the list. This contradicts the assumption that the list was complete.
Note one detail: we are not saying that N is prime. For example 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509. We are only saying it has a prime factor outside the list.
Proof by cases
When the hypotheses split naturally into different situations, you prove the statement in each. What matters is that the cases are exhaustive: they must cover every possibility.
Statement: for every integer n, n² divided by 3 leaves remainder 0 or 1, never 2.
Proof: every integer has the form 3k, 3k + 1 or 3k + 2.
- If n = 3k: n² = 9k² = 3(3k²), remainder 0.
- If n = 3k + 1: n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, remainder 1.
- If n = 3k + 2: n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1, remainder 1.
The three cases cover all integers, so the statement is proved. A practical consequence: a number that leaves remainder 2 when divided by 3 cannot be a perfect square.
Existence proofs
To prove ∃x P(x) there are two routes.
- Constructive: you exhibit a concrete x. "There is a number that can be written as a sum of two cubes in two different ways": 1729 = 1³ + 12³ = 9³ + 10³.
- Non-constructive: you show that some x must exist without identifying it. The pigeonhole principle provides many examples of this kind.
In computing, constructive proofs are especially valuable, because they often correspond to an algorithm that finds the solution.
Counterexamples
To show that a universal statement ∀x P(x) is false, a single x for which P(x) fails is enough. "Every number of the form n² + n + 41 is prime" holds for many small values of n, but for n = 40 you get 40² + 40 + 41 = 1681 = 41², which is not prime. An example does not prove a universal statement; a counterexample is enough to demolish it.
How to choose
| If the statement… | Try first |
|---|---|
| follows "forwards" from the definitions | direct proof |
| is a negation (not rational, does not exist) | contradiction |
| has a more manageable negation | contrapositive |
| depends on parity, remainders, signs | cases |
| asserts existence | explicit construction |
| looks false | look for a counterexample |
In short
- A direct proof starts from definitions translated into algebra.
- In proof by contradiction you negate the statement and look for a contradiction; it suits negative statements.
- With multiple cases, the exhaustiveness of the cases is an essential part of the proof.
- Constructive proofs often amount to an algorithm.
- A single counterexample is enough to refute a universal statement.
