A program that passes 1,000 test cases can still fail on the 1,001st. Testing shows that something works for the inputs you tried; it never shows that it works for every input. Mathematics has the same problem, and its answer is the proof: an argument that leaves no case unchecked.
In the Rules of Inference chapter we saw the small, valid steps (modus ponens, modus tollens, hypothetical syllogism and so on) from which arguments are built. In this chapter we put those steps together into complete proofs. You will learn the standard proof techniques, when to choose each one, how to write them cleanly, and how to spot a broken proof, which is a favourite GATE and interview question.
A proof is a finite sequence of statements, each of which is an axiom, a definition, a previously proved result, or follows from earlier statements by a valid rule of inference, ending with the statement to be proved.
Why Proofs Matter in Computer Science
Proofs are not only for mathematicians. Computer scientists use them every day, often without calling them proofs:
Algorithm correctness: why does binary search always find the key if it is present? Why does Dijkstra's algorithm give shortest paths?
Complexity bounds: why can no comparison-based sort beat n log n comparisons in the worst case?
Security: why is a cryptographic scheme hard to break if factoring is hard?
Compilers and verification: why does an optimisation never change the meaning of a program?
A small table shows why "it worked on many inputs" is not enough. The expression n² + n + 41 looks like a prime-number machine:
n : 0 1 2 3 4 5 ... 39
n² + n + 41 : 41 43 47 53 61 71 ... 1601 (all prime!)
Forty prime values in a row. Yet at n = 40 we get 40² + 40 + 41 = 1681 = 41², which is not prime. Only a proof could have told us the truth in advance.
Vocabulary of Proofs
Term | Meaning |
|---|---|
Axiom (postulate) | A statement assumed to be true without proof, e.g. "for integers a, b: a + b = b + a". |
Definition | The exact meaning of a word. "n is even" means n = 2k for some integer k; "n is odd" means n = 2k + 1 for some integer k. |
Theorem | An important statement that has been proved. |
Lemma | A smaller result proved mainly to help prove a theorem. |
Corollary | A result that follows quickly from a theorem. |
Conjecture | A statement believed true but not yet proved (e.g. Goldbach's conjecture: every even integer greater than 2 is the sum of two primes). |
Most theorems have the shape ∀x (P(x) → Q(x)): "for every x, if P(x) then Q(x)". Mathematicians often leave the "for every" unstated: "if n is odd, then n² is odd" really means "for every integer n, if n is odd then n² is odd". To prove it we take an arbitrary n (we assume nothing about it except P(n)) and show Q(n). Because n was arbitrary, the result holds for all n. This is the rule of universal generalisation from the Rules of Inference chapter.
We will use these facts about integers freely: the sum, difference and product of integers are integers, and every integer is either even or odd but not both.
1. Direct Proof
To prove P → Q directly:
Assume P is true.
Use definitions, algebra and known results to reach Q.
Why is this enough? A conditional P → Q is false only when P is true and Q is false. If we show that P being true forces Q to be true, that bad case can never happen.
Example 1: the square of an odd integer is odd
Theorem. If n is an odd integer, then n² is odd.
Proof. Assume n is odd. By definition, n = 2k + 1 for some integer k. Then
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
Let m = 2k² + 2k, which is an integer. Then n² = 2m + 1, so n² is odd. ∎
Example 2: sum of two rationals is rational
Recall that a real number r is rational if r = p/q for integers p, q with q ≠ 0.
Proof. Let r = a/b and s = c/d with a, b, c, d integers and b, d ≠ 0. Then r + s = (ad + bc)/(bd). The numerator ad + bc is an integer, the denominator bd is an integer, and bd ≠ 0 because neither b nor d is 0. So r + s is rational. ∎
Example 3: AM–GM inequality for two numbers
Theorem. For all real x, y ≥ 0: (x + y)/2 ≥ √(xy).
Proof. The square of any real number is non-negative, so (√x − √y)² ≥ 0. Expanding: x − 2√(xy) + y ≥ 0, i.e. x + y ≥ 2√(xy). Divide by 2. ∎
A useful habit: when you do not know where to start, write out the definitions of everything in the hypothesis. In Example 1 the whole proof grew out of "n = 2k + 1".
2. Proof by Contrapositive
From the Logical Equivalences & Normal Forms chapter, P → Q is logically equivalent to its contrapositive ¬Q → ¬P. So instead of proving P → Q, we may assume ¬Q and prove ¬P with a direct proof.
Use this when the hypothesis P is hard to work with but ¬Q gives you something concrete, typically when Q says "is even", "is irrational", "is not ..." and so on.
Example 4: if n² is even, then n is even
A direct proof gets stuck: from n² = 2k we would need √(2k), which is not helpful.
Proof (contrapositive). We prove: if n is not even, then n² is not even, i.e. if n is odd then n² is odd. That is exactly Example 1. ∎
Example 5: if 3n + 2 is odd, then n is odd
Proof. Contrapositive: assume n is even, n = 2k. Then 3n + 2 = 6k + 2 = 2(3k + 1), which is even. So "n even → 3n + 2 even", which is the contrapositive of the claim. ∎
Example 6: if xy > 25 then x > 5 or y > 5 (for x, y ≥ 0)
Proof. Contrapositive: assume ¬(x > 5 ∨ y > 5), which by De Morgan's law is x ≤ 5 ∧ y ≤ 5. Since 0 ≤ x ≤ 5 and 0 ≤ y ≤ 5, we get xy ≤ 5 · 5 = 25. So xy is not greater than 25. ∎
Notice how De Morgan's law turned an awkward "or" in the conclusion into a friendly "and" in the hypothesis.
Statement | Form | Equivalent to P → Q? |
|---|---|---|
Original | P → Q | — |
Contrapositive | ¬Q → ¬P | Yes |
Converse | Q → P | No |
Inverse | ¬P → ¬Q | No (it is equivalent to the converse) |
Proving the converse instead of the contrapositive is one of the most common mistakes in exams.
3. Proof by Contradiction
To prove a statement S by contradiction:
Assume ¬S (the statement is false).
Derive a contradiction: some statement C together with ¬C (for example "k is even and k is odd", or "0 < 0").
Conclude S.
Why does this work? We showed ¬S → (C ∧ ¬C). The right side is always false, and a conditional with a false conclusion can only be true if its hypothesis is false. So ¬S is false, which means S is true.
To prove a conditional P → Q by contradiction, assume P and ¬Q together and derive a contradiction. (Contrapositive is the special case where the contradiction is "P and ¬P".)
Example 7: √2 is irrational
Proof. Suppose, for contradiction, that √2 is rational. Then √2 = a/b where a, b are integers, b ≠ 0, and the fraction is in lowest terms (a and b have no common factor greater than 1). Every rational number can be written this way.
Squaring: 2 = a²/b², so a² = 2b². Hence a² is even.
By Example 4, a is even. Write a = 2c.
Then 4c² = 2b², so b² = 2c². Hence b² is even, and again b is even.
Now 2 divides both a and b, contradicting "lowest terms". ∎
Example 8: there are infinitely many primes (Euclid)
Proof. Suppose there are only finitely many primes, p1, p2, …, pn. Let N = p1p2⋯pn + 1.
N > 1, so N has at least one prime factor q. (Why? Let q be the smallest divisor of N that is greater than 1. If q were not prime, it would have a divisor d with 1 < d < q, and d would also divide N, contradicting the choice of q.)
q must be one of p1, …, pn, since those are all the primes. So q divides the product p1⋯pn.
q divides N and q divides N − 1 = p1⋯pn, so q divides their difference, 1. But no prime divides 1. Contradiction. ∎
Careful: the proof does not say N itself is prime. For example, 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 × 509. It only says N has a prime factor that is not on the list.
Example 9: rational + irrational = irrational
Proof. Let r be rational and x irrational, and suppose r + x = s is rational. Then x = s − r. The difference of two rationals is rational (same argument as Example 2), so x is rational. Contradiction. ∎
4. Proof by Cases (Exhaustive Proof)
If the hypothesis can be split into cases P1 ∨ P2 ∨ … ∨ Pk that together cover every possibility, prove the conclusion in each case separately. This rests on the tautology
[(P1 ∨ P2 ∨ … ∨ Pk) → Q] ≡ [(P1 → Q) ∧ (P2 → Q) ∧ … ∧ (Pk → Q)]
When the number of cases is small and finite and each case is checked directly (by computing), it is called an exhaustive proof or proof by brute force. Computers are excellent at these.
Example 10: n² + n is always even
Proof. Every integer is even or odd.
Case 1: n = 2k. Then n² + n = 4k² + 2k = 2(2k² + k), even.
Case 2: n = 2k + 1. Then n² + n = (2k + 1)(2k + 2) = 2(2k + 1)(k + 1), even. ∎
(Shorter: n² + n = n(n + 1) is a product of two consecutive integers, one of which is even.)
Example 11: a square leaves remainder 0 or 1 when divided by 4
n = 2k: n² = 4k², remainder 0.
n = 2k + 1: n² = 4k² + 4k + 1 = 4(k² + k) + 1, remainder 1. ∎
Consequence: no integer of the form 4m + 3 (like 3, 7, 11, 1003) is a sum of two squares, because a² + b² mod 4 can only be 0 + 0, 0 + 1 or 1 + 1, i.e. 0, 1 or 2.
Example 12: |xy| = |x| · |y| for all reals
Four cases by the signs of x and y (x ≥ 0 or x < 0, and the same for y). For instance, if x ≥ 0 and y < 0, then xy ≤ 0, so |xy| = −xy = x · (−y) = |x| · |y|. The other three cases are similar. ∎
Without loss of generality (WLOG)
When two cases are identical except that names are swapped, we prove one and say "without loss of generality". In Example 12, the case "x < 0, y ≥ 0" is the same as "x ≥ 0, y < 0" with x and y renamed, so it does not need its own argument. Use WLOG only when the symmetry is genuine.
5. Proving "If and Only If"
P ↔ Q is equivalent to (P → Q) ∧ (Q → P). So a biconditional proof has two parts, and each part may use any technique.
Example 13: n is odd if and only if n² is odd
(→) If n is odd, n² is odd: Example 1 (direct).
(←) If n² is odd, n is odd. Contrapositive: if n is even, n = 2k, then n² = 2(2k²) is even. ∎
For several statements P1, P2, …, Pk that are claimed to be equivalent, it is enough to prove a cycle P1 → P2 → … → Pk → P1. That needs k implications instead of k(k − 1).
6. Existence and Uniqueness Proofs
A statement ∃x P(x) is proved by showing that some x with P(x) exists.
Constructive existence
Exhibit a specific witness. Claim: there is a positive integer that can be written as a sum of two positive cubes in two different ways. Proof: 1729 = 1³ + 12³ = 9³ + 10³ (both equal 1729). ∎
Non-constructive existence
Show that a witness must exist without saying which one it is.
Claim: there exist irrational numbers a and b such that ab is rational.
Proof. Consider √2√2. It is either rational or irrational.
If it is rational, take a = b = √2. Done.
If it is irrational, take a = √2√2 and b = √2. Then ab = √2√2·√2 = √22 = 2, rational. Done. ∎
We proved existence without knowing which pair works. (It is in fact known that √2√2 is irrational, but the proof does not need that.)
Uniqueness
To prove "there is exactly one x with P(x)":
Existence: find an x with P(x).
Uniqueness: assume P(x) and P(y), and show x = y.
Example 14. If a, b are reals with a ≠ 0, the equation ax + b = 0 has a unique solution. Existence: x = −b/a works, since a(−b/a) + b = 0. Uniqueness: if ax + b = 0 and ay + b = 0, then ax = ay; dividing by a (allowed because a ≠ 0) gives x = y. ∎
7. Disproof by Counterexample
To show that ∀x P(x) is false, one x with ¬P(x) is enough. This follows from the negation rule ¬∀x P(x) ≡ ∃x ¬P(x) from the Predicate Logic & Quantifiers chapter.
False claim | Counterexample |
|---|---|
Every prime is odd. | 2 |
n² + n + 41 is prime for every n ≥ 0. | n = 40: 1681 = 41² |
If p is prime, then 2p − 1 is prime. | p = 11: 2047 = 23 × 89 |
For all reals x, x² > x. | x = 1/2 (1/4 < 1/2), or x = 1 |
If a | bc then a | b or a | c. | a = 6, b = 2, c = 3 |
Important asymmetry: one example disproves a universal statement, but no number of examples proves one (unless you check every case of a finite domain).
Computers are very good at hunting for counterexamples. Here is a small, complete Python program:
def is_prime(n):
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
def find_counterexample(claim, candidates):
"""Return the first value for which claim(value) is False, else None."""
for x in candidates:
if not claim(x):
return x
return None
# Claim 1: n*n + n + 41 is prime for every n >= 0
n = find_counterexample(lambda n: is_prime(n * n + n + 41), range(0, 1000))
print("Claim 1 fails at n =", n, "value =", n * n + n + 41)
# Claim 2: if p is prime, then 2**p - 1 is prime
p = find_counterexample(lambda p: not is_prime(p) or is_prime(2**p - 1), range(2, 100))
print("Claim 2 fails at p =", p, "value =", 2**p - 1)
# Claim 3: n*n is odd whenever n is odd (a true statement)
n = find_counterexample(lambda n: n % 2 == 0 or (n * n) % 2 == 1, range(-10**5, 10**5))
print("Claim 3 counterexample:", n)
Output:
Claim 1 fails at n = 40 value = 1681
Claim 2 fails at p = 11 value = 2047
Claim 3 counterexample: None
Notice how Claim 2 is coded: "p prime → 2p − 1 prime" becomes not is_prime(p) or is_prime(2**p - 1), using P → Q ≡ ¬P ∨ Q. For Claim 3, "None" only means no counterexample was found in that range; the proof in Example 1 is what makes it certain.
8. Vacuous and Trivial Proofs
Vacuous proof: if P is always false, then P → Q is true no matter what Q is. Example: "for every integer n, if n² < 0 then n = 42" is true because no integer has n² < 0. Vacuous truth is also why "the empty set is a subset of every set" (you will meet this again in Sets & Set Operations) and why the base case of some induction proofs is immediate.
Trivial proof: if Q is always true, then P → Q is true without using P. Example: "if n is prime, then n² ≥ 0".
Choosing a Technique
Situation | Try first |
|---|---|
Hypothesis gives a usable formula (n = 2k + 1, r = a/b) | Direct proof |
Conclusion is a negative or awkward property ("n is even" from "n² is even") | Contrapositive |
Statement says something does not exist, or is irrational, or is infinite | Contradiction |
Natural split by parity, sign, remainder, or a few values | Cases |
"There exists ..." | Construct a witness (or non-constructive argument) |
"For all ..." and you suspect it is false | Counterexample |
"For every integer n ≥ n0 ..." with a step-by-step structure | Mathematical induction (next chapter) |
Spotting Flawed Proofs
The "1 = 2" trick
Let a = b.
Step 1: a² = ab (multiply by a)
Step 2: a² − b² = ab − b² (subtract b²)
Step 3: (a+b)(a−b) = b(a−b) (factor)
Step 4: a + b = b (divide by a − b)
Step 5: 2b = b (since a = b)
Step 6: 2 = 1 (divide by b)
Step 4 divides by a − b, which is 0. Division by zero is not a valid step, so everything after it is unsupported.
Begging the question (circular reasoning)
"n² even → n even. Proof: n² is even, so n² = 2k. Since n is even, n = 2m, ..." The proof assumes the conclusion ("n is even") halfway through. A proof may never use what it is trying to prove.
Affirming the consequent
"If n is odd then n² is odd. n² = 25 is odd, so n is odd." This uses Q and P → Q to conclude P, which is the invalid pattern ((P → Q) ∧ Q) → P from the Rules of Inference chapter. (Here the conclusion happens to be true, but the reasoning is not valid.)
Common Mistakes
Proving by example. Checking n = 1, 2, 3 does not prove a statement about all n.
Reusing the same letter. "Let m = 2k and n = 2k be even" silently forces m = n. Use different letters: m = 2k, n = 2j.
Proving the converse (Q → P) instead of P → Q or its contrapositive.
Wrong negation in contradiction proofs. The negation of "x > 5 or y > 5" is "x ≤ 5 and y ≤ 5", not "x ≤ 5 or y ≤ 5".
Missing cases. In a proof by cases, the cases must cover every possibility (and checking that they do is part of the proof).
Hidden division by zero or taking square roots of negative numbers.
Starting from the conclusion and working "backwards" to something true. That shows Q → TRUE, which proves nothing. Backwards work is fine as scratch work, but the final proof must run forwards (or every step must be reversible).
Interview and GATE-Style Questions
Q1. To prove "if n² is a multiple of 3 then n is a multiple of 3", which technique is easiest, and how does it go?
Contrapositive. Assume n is not a multiple of 3, so n = 3k + 1 or n = 3k + 2. Then n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, or n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1. In both cases n² leaves remainder 1, so it is not a multiple of 3. (This lemma also proves √3 is irrational, exactly like Example 7.)
Q2. A student proves P → Q by assuming ¬Q and deriving ¬P. Which technique is this, and is it valid?
Proof by contrapositive. It is valid because P → Q ≡ ¬Q → ¬P.
Q3. Which of these statements needs only one example to settle? (a) Prove ∃x P(x). (b) Prove ∀x P(x). (c) Disprove ∀x P(x). (d) Disprove ∃x P(x).
(a) and (c). One witness proves an existential statement, and one counterexample disproves a universal one. (b) and (d) need a general argument, because disproving ∃x P(x) means proving ∀x ¬P(x).
Q4. Prove that the product of two odd integers is odd.
Let a = 2j + 1 and b = 2k + 1 (different letters!). Then ab = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1, which is odd.
Q5. Show that the square of every odd integer leaves remainder 1 when divided by 8.
Let n = 2k + 1. Then n² = 4k² + 4k + 1 = 4k(k + 1) + 1. Since k(k + 1) is a product of consecutive integers, it is even, say 2m. So n² = 8m + 1. (A brute-force check on all odd n below 1000 agrees.)
Q6. In Euclid's proof, is p1p2⋯pn + 1 always prime?
No. 2·3·5·7·11·13 + 1 = 30031 = 59 × 509. The proof only uses the fact that this number has some prime factor not in the list.
Q7. What is wrong with this "proof" that every positive integer is even? "Take n = 2: it is even. Since n was arbitrary, all n are even."
n was not arbitrary; a specific value was chosen. Universal generalisation only applies when nothing special was assumed about the element.
Summary
A proof is a chain of valid inferences from axioms, definitions and earlier results to the claim. Examples alone never prove a universal statement.
Direct: assume P, derive Q. Contrapositive: assume ¬Q, derive ¬P.
Contradiction: assume the negation, reach C ∧ ¬C. Classic uses: √2 irrational, infinitely many primes.
Cases: split into cases that cover everything (parity, sign, remainder); WLOG only for true symmetry.
Biconditional: prove both directions. Existence: constructive (give a witness) or non-constructive. Uniqueness: assume two and show they are equal.
Counterexample: one is enough to disprove a "for all" statement.
Watch for division by zero, circular reasoning, proving the converse, and wrong negations.
Testing finds bugs; proofs show there are none. The next chapter, Mathematical Induction, gives you the most important proof technique for statements about all natural numbers.