Proof Techniques

Definition: Structured mathematical methods used to establish, with logical certainty, that a proposition is true for every case it claims to cover.

How It Works

Direct Proof: assumes the hypothesis P is true and derives the conclusion Q through a chain of valid logical steps, P → Q shown by construction
Every valid proof, regardless of technique, must rest only on previously established axioms, definitions, and theorems, no step is allowed to appeal to intuition alone
Proof by Contrapositive: proves P → Q by instead proving the logically equivalent statement ¬Q → ¬P, useful when the forward direction is hard to reason about directly
Proof by Contradiction: assumes the statement to be proven is false, then derives a logical contradiction from that assumption, forcing the original statement to be true
Proof by Mathematical Induction: establishes a statement P(n) for all natural numbers n in three steps: a base case P(1) (or P(0)), an inductive hypothesis assuming P(k) holds, and an inductive step proving P(k+1) follows from P(k)
Strong Induction extends the inductive hypothesis to assume P(1), P(2), ..., P(k) all hold, not just P(k) alone, useful when P(k+1) depends on more than just the immediately preceding case
Structural induction generalizes ordinary induction to recursively defined structures like trees and lists, proving a base case for the smallest structure and an inductive step for structures built from smaller ones
Proof by Cases splits a statement into an exhaustive set of mutually exclusive scenarios, then proves the statement holds in every scenario individually, common when a claim behaves differently for even versus odd numbers, or positive versus negative values
A proof’s clarity matters almost as much as its correctness, a technically valid proof that skips justifying steps is far less useful to a reader than one that shows its reasoning explicitly
Existence proofs (showing something exists) can be constructive (exhibiting a specific example) or non-constructive (proving existence must follow logically without producing one)
Uniqueness proofs pair with existence proofs to show not just that something exists but that exactly one such object does, typically by assuming two solutions exist and proving they must be equal
Counterexamples disprove a universal claim (for all x, P(x)) with a single instance where P(x) is false, one counterexample is sufficient, no matter how many cases already checked true
Proof by exhaustion checks every case in a finite, enumerable set individually, valid only when the total number of cases is small enough to actually enumerate
The Four Color Theorem is a famous example of computer-assisted proof by exhaustion, verifying thousands of map configurations by machine after the case count exceeded what a human could check by hand
A well-chosen proof technique often shortens the argument dramatically, the same true statement can have a three-line contrapositive proof or a much longer, messier direct one

Choosing a Technique

If the claim looks like…	Try this technique
“For all natural numbers n, P(n)”	Mathematical Induction
“If P, then Q” where P → Q is hard to show directly	Contrapositive (¬Q → ¬P)
“There is no x such that…” or an irrationality claim	Contradiction
“For all x, P(x)” and you suspect it’s false	Search for a Counterexample
A claim splits naturally into distinct scenarios	Proof by Cases
“There exists an x such that P(x)”	Constructive or Non-constructive Existence Proof

Under the Hood

Induction works like an infinite chain of dominoes. The base case knocks over domino 1. The inductive step proves “if domino k falls, domino k+1 falls too,” a single, general rule that applies at every position in the chain, not just once. Together, these two facts guarantee every single domino falls, even though the inductive step is only ever verified once, abstractly, for an arbitrary k, not separately for every actual number.

Skipping the base case is a genuine, common failure, not a technicality. The inductive step alone only proves a chain of implications: P(1) → P(2) → P(3) → .... Without P(1) established as actually true, that chain is a row of dominoes with nothing standing at the front to knock the first one over, the whole argument produces no actual conclusion about any n.

Strong induction changes only the inductive hypothesis, not the base case requirement. Where weak induction assumes just P(k), strong induction assumes P(1) through P(k) all hold, useful for recursive definitions (like the Fibonacci sequence) where P(k+1) genuinely depends on more than one prior case.

Worked Example 1

Given: Prove 1 + 2 + 3 + ... + n = n(n+1)/2 for all n ≥ 1 by induction.
Step: Base case n=1: LHS = 1, RHS = 1(2)/2 = 1, equal. Inductive hypothesis: assume 1+2+...+k = k(k+1)/2. Inductive step: 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)/2, which matches the formula with n = k+1.
Answer: Both the base case and inductive step hold, so the formula is true for all n ≥ 1 by induction.

Worked Example 2

Given: Prove √2 is irrational using proof by contradiction.
Step: Assume √2 = a/b in lowest terms (a, b share no common factor). Then 2 = a²/b², so a² = 2b², meaning a² is even, so a is even, write a = 2c. Substituting: 4c² = 2b², so b² = 2c², meaning b is also even. But a and b were assumed to share no common factor, and both are even, a contradiction.
Answer: The assumption that √2 is rational leads to a contradiction, so √2 must be irrational.

Worked Example 3

Given: Prove “if n² is even, then n is even” using proof by contrapositive.
Step: The contrapositive is “if n is odd, then n² is odd.” Assume n is odd: n = 2k+1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k²+2k) + 1, which is odd by definition.
Answer: The contrapositive holds, so by logical equivalence, the original statement “if n² is even, then n is even” is also proven true.

Worked Example 4

Given: Disprove the claim “all prime numbers are odd” with a counterexample.
Step: Check n = 2. It’s prime (only divisible by 1 and itself) and even.
Answer: 2 is a single counterexample, so the universal claim “all primes are odd” is false, no further checking needed.

Worked Example 5

Given: Prove 2^n > n² for all integers n ≥ 5 using strong induction alongside a base case check.
Step: Base case n=5: 2^5 = 32, 5² = 25, and 32 > 25 holds. Inductive hypothesis: assume 2^k > k² for some k ≥ 5. Inductive step: 2^(k+1) = 2·2^k > 2k². Since k ≥ 5, 2k² ≥ k² + 5k > k² + 2k + 1 = (k+1)² because 5k > 2k+1 whenever k ≥ 1.
Answer: 2^(k+1) > (k+1)² follows, so by induction 2^n > n² holds for every integer n ≥ 5.

Why It Matters

Crucial for proving algorithm correctness, loop invariants, and asymptotic Big-O bounds, induction in particular mirrors how recursive and iterative algorithms actually execute
Underlies formal software verification, proving a program meets its specification for all possible inputs, not just tested ones, requires exactly these techniques
Distinguishes a proof from strong empirical evidence, a pattern that holds for the first million tested cases can still fail on case 1,000,001, only a proof rules that out entirely
Grows increasingly automatable, SAT solvers and proof assistants can now check large swaths of formal proofs mechanically, but choosing which technique to attempt still rests on human judgment
Gives mathematics its defining certainty, a proven theorem holds permanently, unlike an empirical claim that could later be falsified by new evidence
Trains the specific discipline of finding gaps in an argument, a skill that transfers directly to reviewing algorithms, security protocols, and any system that needs to be correct in every case, not just the tested ones
Gives recursive algorithms a correctness argument that mirrors their own structure, a recursive function’s correctness proof is almost always an induction proof shaped exactly like the recursion itself

Common Pitfalls

Failing to prove the base case in an induction proof, invalidating the entire inductive chain even if the inductive step itself is flawless
Assuming what needs to be proven partway through a proof (circular reasoning), especially easy to accidentally do in a long chain of algebraic steps
Confusing “proof by example” with a valid proof, checking a statement holds for several specific values never proves it holds for all values, only a counterexample disproves a universal claim with a single case
Sliding between what’s being assumed and what’s being proven mid-argument, especially in contradiction proofs, where it’s easy to lose track of which statement was assumed false
Misapplying strong induction by only using P(k) when the inductive step actually requires an earlier case like P(k-1), weak induction’s hypothesis isn’t strong enough for such proofs
Treating a proof by contradiction as though the contradiction can come from anywhere, a valid proof must derive the contradiction specifically from the false assumption, not from an unrelated error introduced elsewhere
Writing a proof by cases that isn’t actually exhaustive, missing a scenario means the “proof” hasn’t actually covered every possibility

Comparison

	Direct Proof	Contradiction	Induction	Counterexample
Proves	A specific `P → Q`	Any well-formed statement	`P(n)` for all natural `n`	A universal claim is false
Structure	Forward chain of implications	Assume false, derive contradiction	Base case + inductive step	One disproving instance
Best suited for	Straightforward algebraic/logical claims	Claims hard to prove constructively	Claims indexed by natural numbers	Testing a conjecture before attempting a full proof
Common use case	Geometry, basic algebra	Irrationality proofs, infinitude of primes	Sums, sequences, recursive structures	Disproving over-generalized claims
Number of cases needed	One logical chain	One contradiction	Two, base case and inductive step	One disproving instance
Risk if done wrong	Circular reasoning	Contradiction not tied to the assumption	Missing or unproven base case	Confusing a non-counterexample for a real one

Example

Euclid’s proof that there are infinitely many primes uses contradiction: assume there are finitely many primes p1, ..., pn, then the number (p1 × p2 × ... × pn) + 1 is not divisible by any of them, so either it’s prime itself or has a prime factor not in the original list, contradicting the assumption that the list was complete.

Formal proof assistants like Coq and Lean encode exactly these same techniques, induction, contradiction, case analysis, as machine-checkable tactics, letting a computer verify a proof’s every logical step instead of trusting a human reviewer’s read-through, increasingly used to verify critical software and even published mathematical theorems.

Referenced by

Dig deeper

Spot an error in this note?