Proof Techniques: Induction, Contradiction, and Invariants

Interviewers rarely say "prove this." They say "convince me," and then probe whether your convincing has structure or is hand-waving with confidence. Three argument patterns cover nearly everything; knowing their names and shapes turns "um, it just works" into an answer.

Induction: the ladder

To prove a statement for all $n$: prove the base case, then prove that truth at $n$ forces truth at $n+1$. The blue-eyed islanders question from the practice bank is pure induction — and its interview follow-up ("what did the announcement add?") tests whether you understand why the base case matters: the chain of "if there were only 1…" reasoning needs a common-knowledge floor to stand on.

Two disciplines separate clean induction from sloppy: state the induction hypothesis precisely (what exactly is assumed at $n$?), and watch for the step failing at small $n$ — the famous "all horses are the same color" fallacy breaks exactly at $n=2$, and spotting where a plausible induction breaks is itself a standard interview probe. Strong induction (assume everything up to $n$) is the natural form for games and recursions — the pirate game's backward induction is strong induction running downward.

Contradiction: assume the opposite, find the absurdity

Assume what you want to disprove, derive something impossible. The two showpieces every candidate should be able to perform in ninety seconds:

• $\sqrt 2$ is irrational: suppose $\sqrt2 = p/q$ in lowest terms; then $p^2 = 2q^2$, so $p$ is even, $p = 2k$, then $q^2 = 2k^2$ makes $q$ even too — contradicting lowest terms.
• Infinitely many primes: given any finite list, $p_1p_2\cdots p_k + 1$ is divisible by none of them, so some prime is missing from the list.

The pattern's power in interviews is impossibility: "show no strategy can guarantee X" almost always opens with "suppose one could." The adversary argument that 6 races can't find the top-3 horses (from the question bank) is contradiction wearing work clothes.

Invariants and monovariants: the puzzle-killers

An invariant is a quantity no allowed move changes; if start and target differ on it, the target is unreachable — the mutilated-chessboard argument from the modular-arithmetic lesson. A monovariant moves in only one direction, proving termination: it can't decrease forever if it's a non-negative integer. Classic: people at a party shake hands in some process — track "number of pairs who haven't met"; strictly decreasing, hence the process ends. Algorithmic cousin: proving your loop terminates is exhibiting a monovariant, which links this lesson directly to the coding course's correctness arguments.

Pigeonhole deserves its own line: $n+1$ items in $n$ boxes force a shared box. Instant results: two people in any group of 13 share a birth month; among any 5 points in a unit square, two are within $\sqrt2/2$ (split into 4 sub-squares); the prefix-sums-mod-$n$ argument from the number theory lesson. It proves existence without construction — worth saying explicitly, since interviewers push "but which pair?" to check you know the proof doesn't tell you.

The interview version

The evaluation isn't formality — it's whether your argument has a load-bearing structure someone could attack. So name the move ("by induction on the number of pirates," "suppose not," "consider the following invariant"), state what would break it, and check the smallest case aloud. A trader's version of proof discipline is knowing exactly which assumption your P&L depends on; interviewers treat these puzzles as the dry run for that.