Proof by Contradiction and Mathematical Induction
We have spent this series building forward — if A then B, chain A to B to C, check necessary and sufficient conditions. This chapter introduces two powerful backward strategies: proof by contradiction (assume the opposite, derive a paradox) and mathematical induction (prove it for one step, then prove the next step always works).
Both appear in advanced logical reasoning sections of Korean public exams, and both have an elegance that makes them worth understanding deeply, not just memorizing.
Part 1: Proof by Contradiction
The Strategy
To prove P is true, assume ¬P (P is false) and show that this assumption leads to a contradiction — a statement that is logically impossible (both Q and ¬Q simultaneously).
Since ¬P leads to impossibility, ¬P must be false, therefore P must be true.
Formal structure:
- Assume ¬P.
- Derive valid consequences.
- Reach a contradiction (some statement is both true and false).
- Conclude P is true (because ¬P is impossible).
This method is also called reductio ad absurdum (Latin: “reduction to absurdity”).
Classic Example 1: √2 is Irrational
Claim: √2 is not a rational number.
Proof: Assume the opposite — that √2 is rational. Then √2 = p/q where p and q are integers with no common factors (the fraction is in lowest terms).
Squaring: 2 = p²/q², so p² = 2q². This means p² is even, which means p is even (if p were odd, p² would be odd). Write p = 2k for some integer k. Then (2k)² = 2q² → 4k² = 2q² → q² = 2k². So q² is even, meaning q is also even.
But now both p and q are even — they share a factor of 2. This contradicts our assumption that p/q was in lowest terms.
Contradiction → Our assumption (√2 is rational) is false → √2 is irrational. ∎
Classic Example 2: There Are Infinitely Many Primes
Claim: There is no largest prime number.
Proof: Assume the opposite — that there are finitely many primes: p₁, p₂, …, pₙ (a complete list).
Construct: N = (p₁ × p₂ × … × pₙ) + 1.
N is larger than all listed primes. Is N prime?
- If N is prime, we found a prime not on our “complete” list — contradiction.
- If N is composite, it must have a prime factor. But N divided by any pᵢ leaves remainder 1 — so none of the listed primes divides N. Where is N’s prime factor? It must be an unlisted prime — contradiction.
Either way, our assumption (finitely many primes) leads to contradiction. Contradiction → There are infinitely many primes. ∎
Exam Application: The Liar’s Puzzle
Proof by contradiction is the engine behind the classic “who is lying” exam format.
Problem: Three people each make a statement. Exactly one is lying.
- Alex: “I am telling the truth.”
- Blake: “Alex is lying.”
- Casey: “Blake is lying.”
Who is the liar?
Method: Assume each person is the liar in turn, check for contradictions.
Assume Alex lies:
- Alex is lying → “I am telling the truth” is false → Alex is indeed lying (consistent so far).
- Blake says “Alex is lying” → this is TRUE → Blake is truthful (consistent).
- Casey says “Blake is lying” → but Blake is truthful, so this is FALSE → Casey is lying.
- But we assumed exactly one liar, and both Alex and Casey would be lying. Contradiction.
Assume Blake lies:
- “Alex is lying” is false → Alex is truthful.
- Alex says “I am telling the truth” → consistent (Alex is truthful).
- Casey says “Blake is lying” → Blake is lying, TRUE → Casey is truthful.
- Exactly one liar (Blake). No contradiction. ✅
Assume Casey lies: (You can verify this also creates contradiction.)
Answer: Blake is the liar.
Part 2: Mathematical Induction
The Strategy
Mathematical induction proves that a statement P(n) is true for all natural numbers n ≥ 1 (or some starting value).
Two steps:
- Base case: Prove P(1) is true.
- Inductive step: Assume P(k) is true (the induction hypothesis), then prove P(k+1) is true.
If both steps succeed, P(n) is true for all n ≥ 1.
The Domino Metaphor
Imagine an infinite row of dominoes:
- Base case: The first domino falls (P(1) is true).
- Inductive step: Whenever domino k falls, it knocks over domino k+1.
- Conclusion: All dominoes fall — all P(n) are true.
The key insight: you do not need to check every domino individually. You only need to confirm (1) the first one falls and (2) the falling mechanism propagates.
Classic Example: Sum of First n Natural Numbers
Claim: 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.
Base case (n = 1): 1 = 1(2)/2 = 1. ✓
Inductive step: Assume the formula holds for n = k: 1 + 2 + … + k = k(k+1)/2.
Now prove it for n = k+1: 1 + 2 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)[k/2 + 1] = (k+1)(k+2)/2 = (k+1)((k+1)+1)/2. ✓
This is exactly the formula with n = k+1. Induction complete. ∎
Exam Application: Step-by-Step Verification
Exam problems rarely ask you to perform full induction proofs. Instead, they ask you to verify that an inductive argument is valid:
- Does the base case hold?
- Does the inductive step logically follow?
- Is the conclusion properly bounded?
Pitfall — Vacuous Base Case: If your “base case” is actually impossible or undefined, the induction proves nothing. Always check that P(1) is a meaningful, true statement.
Pitfall — Circular Induction: The inductive step assumes what it is trying to prove. Watch for arguments that say “assuming P(k) is true… therefore P(k) is true” — they have not actually proved P(k+1).
Example 2: 2ⁿ > n (n ≥ 1)
[Base] n = 1: 2¹ = 2 > 1 ✓
[Inductive step] Assume 2ᵏ > k holds.
Therefore ✓
Conclusion: holds for all n ≥ 1. ■
Connecting the Four Methods
| Method | When to use it | Structure |
|---|---|---|
| Direct proof | When you can show P is true in a forward direction | P → Q derived directly |
| Proof by contradiction | When assuming “P is false” makes a contradiction easy to see | ¬P → ⊥ |
| Proof by contrapositive | When the contrapositive (¬Q → ¬P) is easier than a direct proof | ¬Q → ¬P |
| Mathematical induction | When proving an infinite case over the naturals n | P(1) + P(k)→P(k+1) |
Contradiction vs. contrapositive:
- Contrapositive: prove “if not Q, then not P” — forward direction
- Contradiction: assume “P and not Q” → contradiction → so if P then Q — indirect
They feel similar but their structures differ. Do not confuse the two on the exam.
Common Mistakes
In proof by contradiction
Mistake: confusing the assumption with the conclusion — starting from “assume ¬P” but then using P somewhere in the proof, which is circular.
Correct check: follow the logical flow from the assumption (¬P) and confirm it never breaks before reaching the contradiction.
In mathematical induction
Mistake: trying to prove P(k+1) directly in the inductive step → you must use P(k), or it is not induction at all.
Mistake 2: skipping the base case — it is not always n=1; sometimes the problem starts at n=0 or n=2, so check the problem statement.
Practice Problems
Problem 1 (contradiction): Prove that there is no integer n such that n is both even and odd.
Solution
Assume there is such an integer n — both even and odd. Even: n = 2a for some integer a. Odd: n = 2b + 1 for some integer b. Then 2a = 2b + 1, so 2a − 2b = 1, so 2(a−b) = 1. But 2(a−b) is even and 1 is odd. Contradiction. No integer can be both even and odd. ∎
Problem 2 (induction): Prove by mathematical induction that for every natural n,
Solution
[Base] n = 1: left side = 1, right side = 1² = 1 ✓
[Inductive step] Assume .
Left side through the (k+1) term = = right side ✓
Conclusion: holds for all n. ■
Problem 3 (exam liar puzzle): Four colleagues, exactly one is lying.
- Mia: “I am not the liar.”
- Noah: “Mia is telling the truth.”
- Olivia: “Noah is lying.”
- Pita: “Olivia is lying.”
Who is the liar?
Solution
Assume Olivia is the liar:
- Olivia says “Noah is lying” → FALSE → Noah is truthful.
- Noah says “Mia is telling the truth” → TRUE and Noah is truthful → Mia is truthful.
- Mia says “I am not the liar” → TRUE, consistent.
- Pita says “Olivia is lying” → TRUE → Pita is truthful. Exactly one liar (Olivia). No contradiction. ✅
Answer: Olivia is the liar.
Problem 4 (induction base case): Someone claims “For all n ≥ 1, n² + n is odd.” Check the base case.
Solution
Base case n = 1: 1² + 1 = 2, which is even, not odd. The base case fails. The claim is false. (In fact n² + n = n(n+1), which is always even — the product of consecutive integers.)
Key Summary
- Proof by contradiction: ¬P → ⊥ → P
- “Assume the opposite and reach a contradiction → the original claim is true”
Mathematical induction
- Base: confirm P(1) holds
- Inductive step: prove P(k) → P(k+1)
- Conclusion: P(n) holds for every natural n
The difference between them
- Contradiction = indirect proof (drive to a contradiction)
- Induction = domino proof (spread without limit)
Mathematical induction stops being hard the moment you think of dominoes. Two things are visible — the first piece falls (base), and if one falls then the next falls too (inductive step) — and you have proved infinitely many cases in exactly two steps. Proof by contradiction is the wisdom of taking the long way round a road you cannot walk directly: by showing the reverse path is blocked, you prove the direct one was the right road. The next chapter (Ch8) covers practical logic strategies — combining contradiction, truth-value fixing, and chain reasoning.
Oiyo
Editorial DeskThe OIYO editorial desk researches money, law, lifestyle, and self-understanding topics against primary sources and public statistics. Every piece carries source notes and is reviewed on a regular cycle for accuracy and usefulness.