[Beginner → Intermediate] — How to establish that something is true for every case, and the handful of patterns that cover almost everything.

What a proof is

A proof is an argument that convinces a sceptical reader that a statement is true — for all cases, not just the ones you tried.

It’s not a formal derivation in symbolic logic (that’s a formal proof, and almost nobody writes them by hand). It’s prose with rigorous reasoning, written for a human.

The relationship to testing is exact and worth stating. A test checks one input. A property test checks many. A proof checks all of them, including the ones you’d never think of. That’s why proofs are worth the effort for a consensus algorithm and not worth it for a CRUD endpoint — the cost is high and the value scales with how catastrophic an uncovered case would be.

Direct proof

Assume , derive , conclude . The default; try it first.

Claim: If is even, then is even.

Proof. Suppose is even. Then for some integer . So . Since is an integer, is even.

The structure to notice: unpack the definition (“even” → ), do algebra, repack into the definition. Most direct proofs are exactly that, and getting stuck usually means you haven’t unpacked a definition yet.

Proof by contraposition

To prove , prove instead. Same statement — see note 02 — and often far easier.

Claim: If is even, then is even.

Direct attempt: , so … and you’re stuck. Square roots aren’t algebraically pleasant.

Contrapositive: if is odd, then is odd. Suppose . Then , which is odd.

The tell: when the hypothesis is awkward to work with and the negation of the conclusion is concrete, flip it. Here “n is odd” gives you to manipulate; ” is even” gives you a square root.

Proof by contradiction

Assume the statement is false, derive something impossible, conclude it must be true.

Claim: is irrational.

Proof. Suppose not — suppose in lowest terms. Then , so is even, so is even (by the previous result). Write : then , so , so is even too. But then and share a factor of 2, contradicting “lowest terms”.

Powerful, and worth two warnings:

It can obscure. A direct proof usually explains why; a proof by contradiction often just shows the alternative is impossible. Prefer direct when you have the choice.

It’s non-constructive. Proving “a solution exists” by contradiction doesn’t tell you what the solution is. (Constructive mathematics rejects this move entirely, which matters for type theory and proof assistants — a constructive proof is a program that produces the object.)

Where it’s the natural tool: proving something doesn’t exist, or that a set is infinite. Euclid’s proof that there are infinitely many primes is the classic — assume finitely many, multiply them all and add 1, and you’ve produced a number that’s either prime or has a prime factor not in your list.

Proof by cases

Split into exhaustive cases and prove each.

Claim: For any integer , is even.

Proof. Case 1: even. , so , even. Case 2: odd. , so , even. Every integer is even or odd, so the cases are exhaustive.

The only thing that can go wrong is missing a case, so state explicitly why yours are exhaustive. This is precisely the discipline a compiler enforces with exhaustiveness checking on a match — and the reason Rust’s insistence on it catches real bugs.

Counterexample

To disprove a universal claim, produce one instance where it fails. That’s the whole method.

Claim: Every odd number is prime.
Disproof: 9.

Asymmetry worth remembering: disproving takes one example; proving it takes a general argument. This is why finding a bug is easy and proving there are none is hard, and it’s the same asymmetry as falsifiability in science.

And it’s why working proves nothing. A famous case: is prime for every from 0 to 39, and composite at 40.

Proof by induction

The most important technique in computer science, and it gets its own note because recursion is the same idea.

Structure:

  1. Base case — prove
  2. Inductive step — prove for arbitrary
  3. Conclude for all

The domino intuition: the base case knocks the first one over; the inductive step guarantees each knocks over the next.

Fully developed in note 05, including strong induction and structural induction.

Existence and uniqueness

Existence — show something exists. Constructive proofs exhibit one; non-constructive proofs show one must exist without producing it.

The pigeonhole principle gives beautifully non-constructive proofs: some two people in London have the same number of hairs on their heads, and you’ll never learn who. → Combinatorics

Uniqueness — the standard move: assume two objects and both satisfy the property, then prove .

Proving programs correct

Where this becomes concrete, and the reason CS students learn it.

Loop invariants are induction, exactly. A property that:

  1. Holds before the loop starts (base case)
  2. Is preserved by each iteration (inductive step)
  3. Combined with the exit condition, gives what you wanted (conclusion)

Binary search. Invariant: if the target is in the array, it’s within [lo, hi].

Initially lo=0, hi=n-1 — trivially true. Each iteration discards a half that provably can’t contain the target, so the invariant survives. On exit, the range is empty or has been found — so if it wasn’t found, it wasn’t there.

Termination: hi - lo strictly decreases and is bounded below, so the loop ends.

Correctness needs both parts:

Partial correctness — if it terminates, the answer is right. Termination — it does terminate.

They’re separate obligations, and proving termination generally is impossible — that’s the halting problem. → Decidability

The practical technique is a variant: a quantity that strictly decreases each iteration and cannot go below a bound. hi - lo above; the remaining list length in a recursion. If you can’t name the variant, you may not have termination — and that’s a genuinely useful review question to ask about any loop that isn’t obviously bounded.

Writing a proof

State what you’re proving. Precisely, with all quantifiers.

Say which technique you’re using. “We proceed by induction on .” The reader shouldn’t have to reverse-engineer your structure.

Define your notation before using it.

Justify each step, or make it obviously mechanical. “Therefore” needs to be earned.

Say where each hypothesis is used. A proof that never uses a hypothesis is proving something stronger — or is wrong.

End it. or QED.

A proof is writing, and the same rules apply as anywhere else: clarity over cleverness, point first, and a reader who doesn’t have your context. → Scientific Writing Craft

Common errors

Proving the converse. You set out to prove and prove . The commonest error there is, and easy to miss in your own work.

Circular reasoning. Using the conclusion, usually disguised.

Assuming what’s to be proven in the inductive step. You may assume — that’s the hypothesis. You may not assume , which is what you’re proving.

Examples as proof. Any number of cases is not all cases.

Losing generality. “Let be an even integer” when the claim was about all integers.

Division by a possibly-zero quantity, and taking square roots without both signs. Both quietly discard cases.

A missing case, which is the failure mode of proof by cases and of pattern matching alike.


↑ Back to Discrete Mathematics