Proof and Induction: Covering Infinitely Many Cases

A function taking two 32-bit integers has $2^{64}$ possible inputs, about $1.8 \times 10^{19}$. At a billion cases per second, exhaustive testing finishes in 585 years. Every test suite ever written samples.

A proof does something categorically different. It establishes a property for every input at once, including inputs that will never be constructed, by arguing about the structure of the problem rather than checking instances.

Key idea: Testing and proof answer different questions. Testing asks "did it work on these?" and is cheap, empirical and always incomplete. Proof asks "must it work on all?" and is expensive, deductive, and complete within its assumptions. Serious systems use both, and knowing which one a claim rests on tells you what its failure would look like.

A proof is a finite chain of statements running from things already accepted to the claim, where every link is a step nobody can dispute.

Definition: An axiom is assumed without argument. A theorem is something derived. A proof is the derivation. "Derived" means each step follows by a rule of logic or a previously established result, with nothing skipped that a determined sceptic could question.

The standard is social as much as formal: a proof convinces a careful reader who is actively trying to break it. That is why proofs are written in prose rather than symbols, and why "it is obvious that" is where errors live.

Three shapes cover most of what you will read: prove it directly, assume the opposite and derive nonsense, or prove it for a base case and show it propagates. The rest of this lesson is those three.

Assume the hypothesis, apply definitions, arrive at the conclusion. Most proofs are this, and the craft is in unfolding the definitions at the right moment.

Claim. If $n$ is odd then $n^2$ is odd.

Proof. $n$ odd means $n = 2k + 1$ for some integer $k$, by definition. Then

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Since $2k^2 + 2k$ is an integer, $n^2$ has the form $2m + 1$ and is therefore odd. $\blacksquare$

Notice where the work happened: at "means", where the word odd became an equation. Definitions are not preamble to a proof, they are the machinery of it, and a proof that never unfolds one is usually not a proof.

To prove a statement, assume it is false and derive something impossible. The assumption must then have been wrong.

Claim. There are infinitely many primes.

Proof. Suppose not: the primes are a finite list $p_1, p_2, \dots, p_k$. Form

$N = p_1 p_2 \cdots p_k + 1$

Dividing $N$ by any $p_i$ leaves remainder 1, so no prime on the list divides $N$. But every integer above 1 has a prime factor, so $N$ has one, and it is not on the list. The list was supposed to be complete. Contradiction, so no finite list exists. $\blacksquare$

Gotcha: $N$ is not claimed to be prime. That misreading is extremely common. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$, which is composite, and the proof still works: 59 is a prime that was missing from the list.

To prove $P(n)$ holds for all $n \geq n_0$, prove two things:

$\textbf{Base case: } P(n_0) \qquad\qquad \textbf{Inductive step: } P(k) \Rightarrow P(k+1)$

The base case starts the chain and the inductive step keeps it going, so every $n$ is reached in finitely many hops.

Claim. $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

Base. $n = 1$: the left side is 1, the right side is $1 \cdot 2 / 2 = 1$.

Step. Assume it holds for $k$. Then

$1 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$

which is the formula at $k+1$. $\blacksquare$

The assumption $P(k)$ is the induction hypothesis. Using it is the whole point, not circular reasoning: you are proving an implication, not asserting $P(k)$.

Both failures produce a proof that reads convincingly.

Missing base case. Take $P(n)$: "$n = n + 1$". The inductive step is fine, since adding 1 to both sides of $k = k+1$ gives $k+1 = k+2$. There is simply no base case, and without one the chain starts nowhere. A step that propagates truth propagates falsehood equally well.

A step that fails at one place. The classic: "all horses are the same colour". Base case, one horse, holds. Step: given $k+1$ horses, drop the last to get $k$ of one colour, drop the first to get $k$ of one colour, and the overlapping horses tie the two groups together. This fails at exactly $k = 1$, where the two groups of one horse do not overlap, so the chain breaks at the first hop and never reaches 3.

Gotcha: "The inductive step works for large $k$" is not enough. It must work for every $k$ from the base case upward, and the small cases are where it usually does not.

Sometimes $P(k)$ alone is not enough to reach $P(k+1)$, and you need every earlier case. Strong induction assumes $P(m)$ for all $m < k$ and proves $P(k)$ from that.

Claim. Every integer $n > 1$ is a product of primes.

Proof. Take $n > 1$ and assume the claim for every smaller integer above 1. Either $n$ is prime, and it is a product of one prime, or $n = ab$ with $1 < a, b < n$. Both $a$ and $b$ are smaller, so by the hypothesis each is a product of primes, and concatenating those factorisations gives one for $n$. $\blacksquare$

In practice: Strong induction is what recursion on subproblems needs. Merge sort's correctness argument is exactly this shape: assume both halves sort correctly, whatever their sizes, then show merging two sorted lists yields a sorted list. The recursion tree is the induction, running downward.

A loop invariant is a statement true before the loop and preserved by each iteration. Establishing one is a base case plus an inductive step, applied to program state.

def maximum(xs):
    best = xs[0]
    # INVARIANT: best is the maximum of xs[0:i+1]
    for i in range(1, len(xs)):
        if xs[i] > best:
            best = xs[i]
    return best

Initialisation. Before the loop, $i = 0$ and best is the maximum of a one-element slice. True.

Maintenance. If best is the maximum of xs[0:i], then after comparing against xs[i] it is the maximum of xs[0:i+1]. True.

Termination. The loop exits with $i$ at the end, so the invariant says best is the maximum of the whole list, which is the postcondition.

Those three steps are a proof of correctness for every input list, not for the ones your tests happened to use.

Proof and refutation are asymmetric. A universal claim needs an argument covering everything; refuting it needs one instance.

Key idea: Forty passing cases is a test suite. It is evidence, and it is not proof. When a pattern holds for every case you checked, the honest position is that you have not found a counterexample yet.

Proof is complete only within its assumptions, and the assumptions are where real systems fail.

Every published proof of correctness sits on assumptions of this kind, and famous failures usually come from one of them rather than from a flawed argument.

Mechanising the checking is what proof assistants and model checkers do, and that is the subject of the separate Formal Verification course in this catalogue. This lesson gives you the reasoning those tools automate; the reason to learn it by hand first is that a tool will happily verify a specification that says the wrong thing.