Chapter 22. Proof and Induction

Volume 3: Discrete and Probabilistic Mathematics · Part VI: Discrete Mathematics

A program that passes a thousand tests can still be wrong; a statement that holds for forty cases can fail on the forty-first. This chapter is about the one tool that settles a question for every case at once: proof. We start with why checking examples is not enough, take apart what a proof actually is, and then build a toolkit of techniques: direct proof, contrapositive, contradiction, cases, and counterexamples. The second half is devoted to mathematical induction, the technique that is to proof what recursion is to programming, and ends by using the same ideas to prove that real code (binary search, insertion sort) is correct.

Where this chapter sits

You need: integer arithmetic and divisibility words like even, odd and factor (Chapter 1), confident algebraic manipulation, especially expanding and factoring (Chapter 4, Chapter 7), and the logic vocabulary of Chapter 21: implication, contrapositive, negation, and the quantifiers $\forall$ and $\exists$. If Chapter 21 is shaky, read its sections on the conditional and on negating quantifiers first; this chapter leans on them constantly.

This chapter unlocks: every chapter that says "we can show that". Most directly, Chapter 23 (where the Euclidean algorithm and RSA need correctness proofs), Chapter 24 (counting arguments and identities proved by induction), Chapter 25 (proofs about trees and paths), and Chapter 14 (where sum formulas reappear). For a programmer it also unlocks a habit: reasoning about code with invariants rather than only with test cases.

22.1. Why prove anything?

22.1.1. The problem

Here is a formula that looks like a prime-number generator:

\[f(n) = n^2 + n + 41.\]

Try it. $f(0) = 41$, prime. $f(1) = 43$, prime. $f(2) = 47$, prime. $f(3) = 53$, prime. $f(4) = 61$, prime. Keep going and you will find prime after prime. Leonhard Euler noticed this in 1772. If you were writing a unit test for the claim "$f(n)$ is always prime", you would probably stop at ten cases and declare victory. A more careful engineer might check a hundred.

Let the computer check:

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

for n in range(100):
    value = n * n + n + 41
    if not is_prime(value):
        print(f"n = {n}: {value} is composite")
        break
else:
    print("no counterexample below 100")

n = 40: 1681 is composite

Forty consecutive successes, and then $f(40) = 1681 = 41^2$. In hindsight it is obvious: when $n = 40$,

\[\begin{aligned} f(40) &= 40^2 + 40 + 41 \\ &= 40 \cdot 40 + 40 + 41 \\ &= 40(40 + 1) + 41 \qquad\text{(factor 40 out of the first two terms)} \\ &= 40 \cdot 41 + 41 \\ &= 41(40 + 1) = 41^2. \qquad\text{(factor out 41)} \end{aligned}\]

And $f(41) = 41^2 + 41 + 41 = 41 \cdot 43$ is plainly divisible by 41 too.

Bar chart of n squared plus n plus 41; all blue (prime) up to n=39, then red at n=40, 41 and 44

Figure 198. Forty successes, then failure: n² + n + 41 for n = 0 to 45. Blue bars are prime, red bars are composite.

22.1.2. Intuition: evidence versus certainty

Checking examples gives you evidence. A proof gives you certainty. The difference is the difference between "it works on my machine" and "it works on every input the type system allows".

Mathematics cares about statements of the form "for all $n$", and "all" is infinitely many. No finite amount of testing covers infinitely many cases. A proof is a finite argument that covers them all at once, because it reasons about a general $n$ rather than any particular one.

That is also why a single failing case is decisive. "For all $n$, $f(n)$ is prime" is destroyed by one $n$ that fails. Proving a universal claim is hard; disproving one needs just one counterexample.

Theorem, lemma, corollary, conjecture

A theorem is a statement that has been proved. It is usually an important result.
A lemma is a smaller proved statement used as a stepping stone towards a theorem (Greek lemma, "something taken for granted").
A corollary is a statement that follows quickly from a theorem just proved.
A conjecture is a statement believed to be true but not yet proved, such as "every even number greater than 2 is the sum of two primes" (Goldbach’s conjecture).
An axiom is a statement accepted without proof as a starting point, such as "for any integers $a, b$, $a + b = b + a$".
A proof is a chain of statements, each justified by axioms, definitions, earlier results or logical rules, that ends at the claim being proved.

Testing shows the presence of bugs, not their absence

Edsger Dijkstra’s famous line ("program testing can be used to show the presence of bugs, but never to show their absence") is the Euler polynomial in software form. A test suite samples the input space; a proof covers it. In practice engineers combine both: tests catch the bugs you can imagine, proofs (or proof-like reasoning with invariants and types) rule out whole classes of bugs you cannot. Property-based testing tools such as Python’s Hypothesis sit in between: they search hard for counterexamples, which is exactly what you should do before attempting a proof.

Conjectures that failed very late

The Euler polynomial fails at 40. Some patterns hold for far longer. In 1919 George Pólya conjectured that, for every $N \ge 2$, at least half of the numbers up to $N$ have an odd number of prime factors (counted with repetition). It was checked extensively by hand and was widely believed. The smallest counterexample, found by computer in 1980, is $N = 906{,}150{,}257$. No amount of hand testing would ever have found it.

22.1.3. Where you’d use this

Proof is not only for mathematicians. Wherever a mistake is expensive and the cases are too many to test, people reach for it.

Hardware. In 1994 Intel’s Pentium processor was found to divide slightly wrongly for rare inputs: 4,195,835 / 3,145,727 came out as 1.333739 instead of 1.333820. The flaw sat in five missing entries of a lookup table that random testing had not hit. Replacing the chips cost Intel a $475 million charge, and the company turned heavily to machine-checked proofs for its floating-point hardware afterwards.
Distributed systems. Engineers at Amazon Web Services write precise specifications of protocols (in the language TLA+) and check them exhaustively. In one published case a model checker found a bug in a DynamoDB replication design whose shortest triggering sequence was 35 steps long, far deeper than any test or code review had reached.
Engineering and everyday reasoning. A structural calculation showing that a beam carries its design load is a direct proof from stated assumptions (the material strengths, the load cases); the safety factor exists because the assumptions, not the logic, are uncertain. In daily life the same skill is spotting when an argument jumps from "it worked the last five times" to "it always works".

US curriculum

Most US students first meet formal proof in high-school Geometry (typically grade 9 or 10), in the form of "two-column proofs" (statements on the left, reasons on the right). Algebraic proof and induction appear in some Algebra II and Precalculus courses, especially honors tracks, but are mostly taught in a college Discrete Mathematics course, often the first-year course for computer-science majors.

22.2. Anatomy of a proof

22.2.1. The problem

Claim: the sum of two odd numbers is even. You "know" this, and you can check that $3 + 5 = 8$ and $7 + 11 = 18$. But how would you prove it, for every pair of odd numbers?

The first obstacle is not cleverness; it is precision. To prove anything about odd numbers you need a definition of "odd" that you can compute with. "Not divisible by 2" is true but hard to manipulate. "Ends in 1, 3, 5, 7 or 9" depends on base ten. The definition mathematicians use is algebraic.

Even, odd, divides

$\mathbb{Z}$ (blackboard-bold Z, from German Zahlen, "numbers") is the set of all integers $\ldots, -2, -1, 0, 1, 2, \ldots$. $\mathbb{N}$ is the natural numbers; in this chapter $\mathbb{N} = \{0, 1, 2, \ldots\}$.
An integer $n$ is even if $n = 2k$ for some integer $k$.
An integer $n$ is odd if $n = 2k + 1$ for some integer $k$.
For integers $a \neq 0$ and $b$, we say $a$ divides $b$, written $a \mid b$, if $b = a k$ for some integer $k$. So $3 \mid 12$ (because $12 = 3 \cdot 4$) but $3 \nmid 13$. Note that $a \mid b$ is a statement (true or false), not a number; do not confuse it with $a / b$.
Every integer is either even or odd, and never both. (This follows from division with remainder: dividing by 2 leaves remainder 0 or 1.)

22.2.2. Intuition

A proof is like a program that takes the hypotheses as input and produces the conclusion as output, where each line must "type-check" against a definition, an earlier result or a rule of logic. The definitions are the API. A proof that says "odd numbers are, like, not even, so…" does not compile. A proof that says "let $a = 2j + 1$" does.

Here is the proof of the claim, written in the standard style.

Claim. If $a$ and $b$ are odd integers, then $a + b$ is even.

Proof. Let $a$ and $b$ be odd integers. By the definition of odd, there are integers $j$ and $k$ with $a = 2j + 1$ and $b = 2k + 1$. Then

\[\begin{aligned} a + b &= (2j + 1) + (2k + 1) \\ &= 2j + 2k + 2 \qquad\text{(rearrange)} \\ &= 2(j + k + 1). \qquad\text{(factor out 2)} \end{aligned}\]

Since $j + k + 1$ is an integer, $a + b$ is two times an integer, so $a + b$ is even by definition. $\blacksquare$

22.2.3. The parts, named

Look at the structure:

Statement of the claim, as an implication "if (hypotheses) then (conclusion)".
Assume the hypotheses for arbitrary objects: "Let $a$ and $b$ be odd integers." Note the word arbitrary: we did not pick $a = 3$. Whatever we conclude about this unnamed $a$ therefore holds for every odd $a$. This is how a finite argument covers infinitely many cases.
Unpack definitions into algebra: $a = 2j + 1$.
Manipulate towards the form the conclusion needs: $2(\text{integer})$.
Repack into the conclusion’s definition: "so $a + b$ is even".
Mark the end: $\blacksquare$, or "QED".

Notice one subtle point: we used different letters $j$ and $k$. Writing $a = 2k + 1$ and $b = 2k + 1$ would secretly assume $a = b$, and the "proof" would only cover adding a number to itself.

QED and the tombstone

QED abbreviates the Latin quod erat demonstrandum, "which was to be demonstrated". Modern texts usually end a proof with a small filled square $\blacksquare$, called a tombstone or Halmos symbol after the mathematician Paul Halmos who popularised it. Either mark says "the proof is complete; you can stop checking here".

Proof vocabulary you will see

"Let …" introduces an arbitrary object with stated properties.
"Suppose …" or "Assume …" introduces a hypothesis, possibly temporary (as in proof by contradiction).
"Without loss of generality (WLOG)" means "the other case is identical by symmetry, so we treat only this one".
"It suffices to show …" means "if we prove this simpler thing, the original claim follows".
"Hence", "thus", "therefore", "it follows that" mark a step derived from earlier lines.
"if and only if" (iff, $\Leftrightarrow$) requires proving two directions: $P \Rightarrow Q$ and $Q \Rightarrow P$.

Two-column proofs in high-school geometry

US Geometry courses (grades 9–10) teach the same anatomy in table form: a "Statements" column and a "Reasons" column, where each reason must be a given, a definition, a postulate or a previously proved theorem. It is a good discipline. Mathematicians write proofs in paragraphs, but every sentence should still have an implicit "reason" you could write in the right-hand column.

22.3. Direct proof

22.3.1. The method

The sum-of-odds proof was a direct proof: to prove $P \Rightarrow Q$, assume $P$ and derive $Q$ by a chain of valid steps. It is the default technique; reach for it first.

Example 113. Procedure — Direct proof of "if P then Q"

Input: a claim of the form "for all $x$, if $P(x)$ then $Q(x)$".

Steps:

Write "Let $x$ be arbitrary and suppose $P(x)$."
Replace every term in $P(x)$ by its definition (introduce new variables for any "there exists").
Write down what $Q(x)$ means by definition: this is your target form.
Manipulate the information from step 2 until it matches the target form from step 3. If stuck, work backwards from the target on scrap paper, then write the steps forwards.
Conclude "therefore $Q(x)$" and mark the end.

Output: a proof that $P(x) \Rightarrow Q(x)$ for every $x$.

22.3.2. Worked example 1: the square of an odd number is odd

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

Target form: $n^2 = 2(\text{integer}) + 1$.

Proof. Let $n$ be odd, so $n = 2k + 1$ for some integer $k$. Then

\[\begin{aligned} n^2 &= (2k + 1)^2 \\ &= 4k^2 + 4k + 1 \qquad\text{(expand: } (a+b)^2 = a^2 + 2ab + b^2\text{)} \\ &= 2(2k^2 + 2k) + 1. \qquad\text{(factor 2 from the first two terms)} \end{aligned}\]

Since $2k^2 + 2k$ is an integer, $n^2$ is odd. $\blacksquare$

22.3.3. Worked example 2: divisibility is transitive

Claim. For integers $a, b, c$ with $a, b \neq 0$: if $a \mid b$ and $b \mid c$, then $a \mid c$.

Target form: $c = a \cdot (\text{integer})$.

Proof. Suppose $a \mid b$ and $b \mid c$. By definition there are integers $r$ and $s$ with $b = ar$ and $c = bs$. Substitute the first into the second:

\[\begin{aligned} c &= bs \\ &= (ar)s \qquad\text{(substitute } b = ar\text{)} \\ &= a(rs). \qquad\text{(associativity of multiplication)} \end{aligned}\]

Since $rs$ is an integer, $a \mid c$. $\blacksquare$

22.3.4. Worked example 3: a geometric direct proof of Gauss’s sum

Direct proofs need not be algebra. Here is a claim we will prove again by induction later:

\[1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.\]

Draw the sum as a staircase of squares: one square in the first row, two in the second, up to $n$ in the last. Take a second copy, rotate it by 180°, and fit it against the first. The two staircases tile an $n \times (n+1)$ rectangle. So twice the sum is $n(n+1)$, and the sum is $n(n+1)/2$.

Blue staircase of 1 to 5 squares and orange rotated copy forming a 5 by 6 rectangle

Figure 199. Two copies of the staircase 1 + 2 + … + n form an n by (n + 1) rectangle (shown for n = 5).

The algebraic version of the same idea: write the sum forwards and backwards, and add column by column.

\[\begin{aligned} S &= 1 + 2 + \cdots + (n-1) + n \\ S &= n + (n-1) + \cdots + 2 + 1 \\ 2S &= (n+1) + (n+1) + \cdots + (n+1) + (n+1) \qquad\text{(each column sums to } n+1\text{)} \\ 2S &= n(n+1) \qquad\text{(there are } n \text{ columns)} \\ S &= \frac{n(n+1)}{2}. \end{aligned}\]

Gauss and the schoolroom sum

The story (probably embellished in the retelling) is that the young Carl Friedrich Gauss, set the task of adding 1 to 100 to keep him quiet, wrote 5050 on his slate almost at once, having paired 1 with 100, 2 with 99, and so on: 50 pairs each summing to 101. Whether or not it happened, the pairing trick is exactly the forwards-and-backwards argument above.

Working backwards, writing forwards

A common mistake is to start from the conclusion and manipulate until you reach something true, such as

$\quad n^2 \text{ is odd} \Rightarrow \ldots \Rightarrow 1 = 1, \text{ which is true, so done.}$

This proves nothing: you can derive a true statement from a false one ($-1 = 1$ squares to $1 = 1$). Working backwards is a fine way to discover a proof, but the written proof must run from hypotheses to conclusion, and every step must be valid in that direction.

Proof by example is not proof

"$3 + 5 = 8$, which is even, so the sum of two odds is even" is not a proof of a universal statement. Examples are excellent for understanding and for finding the right algebra, but they belong on scrap paper. (An example is a complete proof of an existence claim, such as "there is an even prime": exhibit 2, done.)

22.4. Proof by contrapositive

22.4.1. The problem

Claim: if $n^2$ is even, then $n$ is even.

Try a direct proof. Suppose $n^2 = 2k$. Then $n = \sqrt{2k}$… and now what? Square roots are awkward, and there is no obvious way to show $\sqrt{2k}$ is an even integer. The direct route is stuck.

22.4.2. Intuition

Recall from Chapter 21 that an implication $P \Rightarrow Q$ is logically equivalent to its contrapositive $\neg Q \Rightarrow \neg P$. "If it rained, the ground is wet" says exactly the same as "if the ground is dry, it did not rain". Both statements rule out the same single situation: $P$ true and $Q$ false.

So instead of proving "$n^2$ even $\Rightarrow$ $n$ even" we may prove "$n$ not even $\Rightarrow$ $n^2$ not even", that is, "$n$ odd $\Rightarrow$ $n^2$ odd". And we have already proved that in the previous section. The hypothesis "$n$ is odd" gives us something concrete to work with ($n = 2k+1$), whereas "$n^2$ is even" gave us a square root.

Contrapositive, converse, inverse

For the implication $P \Rightarrow Q$ ("if $P$ then $Q$"):

Contrapositive: $\neg Q \Rightarrow \neg P$. Always equivalent to the original.
Converse: $Q \Rightarrow P$. Not equivalent in general.
Inverse: $\neg P \Rightarrow \neg Q$. Not equivalent in general (it is the contrapositive of the converse).

The symbol $\neg$ means "not". See Chapter 21 for the truth tables.

22.4.3. Worked example 1

Claim. For every integer $n$, if $n^2$ is even then $n$ is even.

Proof (by contrapositive). We prove the equivalent statement: if $n$ is odd then $n^2$ is odd. Let $n$ be odd, so $n = 2k + 1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. Hence, by contraposition, if $n^2$ is even then $n$ is even. $\blacksquare$

We will use this as a lemma in the proof that $\sqrt 2$ is irrational.

22.4.4. Worked example 2: a pigeonhole-flavoured claim

Claim. If $x$ and $y$ are real numbers with $x + y \ge 100$, then $x \ge 50$ or $y \ge 50$.

Directly, it is not clear where to start: "or" conclusions are awkward because you do not know which half holds.

The contrapositive negates both sides. By De Morgan’s law, $\neg(x \ge 50 \lor y \ge 50)$ is $x < 50 \land y < 50$. So the contrapositive is: if $x < 50$ and $y < 50$, then $x + y < 100$.

Proof (by contrapositive). Suppose $x < 50$ and $y < 50$. Adding the two inequalities,

\[x + y < 50 + 50 = 100.\]

So $x + y < 100$, which is the negation of the hypothesis. $\blacksquare$

22.4.5. When to choose the contrapositive

Use the contrapositive when:

the conclusion $Q$ is a negative ("is not divisible", "is irrational") or an "or", so that $\neg Q$ is a positive, concrete fact;
the hypothesis $P$ is hard to unpack (a square, a square root, an inequality in the wrong direction), while $\neg Q$ is easy.

Proving the converse by mistake

The classic error is to prove $Q \Rightarrow P$ and claim you proved $P \Rightarrow Q$. For example, to show "if $n^2$ is even then $n$ is even" you might write "let $n = 2k$; then $n^2 = 4k^2$ is even". That proves the converse: "if $n$ even then $n^2$ even". True, but not what was asked. Always write the claim you are proving at the top, and check that your first line assumes its hypothesis.

Contrapositives in code review

Guard clauses are contrapositives. A function whose contract is "if the input is valid, return a result" is often written as "if the input is not valid, return early / raise". When you reason "this branch can only be reached if user is not None`", you are using the contrapositive of "if `user is None we returned at line 3". Static analysers and type checkers do the same reasoning when they narrow a variable’s type after an if test.

22.5. Proof by contradiction

22.5.1. The problem

Is $\sqrt 2$ a fraction? Your calculator says $\sqrt 2 \approx 1.41421356$, and decimals that stop are fractions, but the calculator’s display stops only because it ran out of digits. The claim "$\sqrt 2$ is irrational" is a negative: it says there is no pair of integers $p, q$ with $\sqrt2 = p/q$. How can you prove that something does not exist, when you cannot check all the infinitely many pairs?

22.5.2. Intuition

Assume the opposite, and follow the consequences until something impossible happens. If assuming $\neg S$ leads to a statement that is definitely false (such as "this number is both even and odd", or "$1 < 0$"), then $\neg S$ cannot be true, so $S$ is true.

This is how a debugger thinks: "suppose this pointer really were null here; then line 40 would have crashed; but line 40 ran; so the pointer was not null". It is also how a detective thinks.

Rational, irrational, lowest terms

A real number is rational if it equals $p/q$ for some integers $p, q$ with $q \ne 0$. The set of rationals is written $\mathbb{Q}$ (for quotient).
A real number that is not rational is irrational. Examples: $\sqrt 2$, $\pi$, $e$.
A fraction $p/q$ is in lowest terms if $p$ and $q$ have no common factor greater than 1. Every rational number can be written in lowest terms (divide top and bottom by their greatest common divisor; see Chapter 23).
A contradiction is a statement that is false by its form, such as $R \land \neg R$ ("R and not R").

22.5.3. The method

Example 114. Procedure — Proof by contradiction

Input: a statement $S$ to prove.

Steps:

Write "Suppose, for contradiction, that $\neg S$." State $\neg S$ precisely (use Chapter 21 rules to negate quantifiers and connectives).
Unpack definitions in $\neg S$ to get concrete objects and equations.
Derive consequences until you reach a contradiction: some statement $R$ together with its negation $\neg R$, or a known falsehood.
Conclude "This is a contradiction, so $\neg S$ is false, and therefore $S$ is true."

Output: a proof of $S$.

22.5.4. Worked example 1: $\sqrt 2$ is irrational

Claim. $\sqrt 2$ is irrational.

Proof. Suppose, for contradiction, that $\sqrt 2$ is rational. Then we can write $\sqrt 2 = p/q$ where $p, q$ are positive integers and the fraction is in lowest terms, so $p$ and $q$ have no common factor greater than 1.

\[\begin{aligned} \sqrt 2 &= \frac{p}{q} \\ 2 &= \frac{p^2}{q^2} \qquad\text{(square both sides)} \\ 2q^2 &= p^2. \qquad\text{(multiply both sides by } q^2\text{)} \end{aligned}\]

So $p^2$ is two times an integer, i.e., $p^2$ is even. By the lemma proved by contrapositive in Section 22.4, $p$ is even. Write $p = 2r$ and substitute:

\[\begin{aligned} 2q^2 &= (2r)^2 = 4r^2 \\ q^2 &= 2r^2. \qquad\text{(divide both sides by 2)} \end{aligned}\]

So $q^2$ is even, and by the same lemma $q$ is even.

Now $p$ and $q$ are both even, so 2 is a common factor greater than 1. This contradicts our choice of $p/q$ in lowest terms. Hence $\sqrt 2$ is not rational. $\blacksquare$

Notice how the pieces of the chapter fit together: a direct proof (odd squared is odd) gave a contrapositive lemma ($n^2$ even implies $n$ even), which powered a contradiction. Real mathematics is built from lemmas like this, much as software is built from tested functions.

The secret of the Pythagoreans

The discovery that the diagonal of a unit square is not a ratio of whole numbers is attributed to the Pythagorean school in ancient Greece, whose philosophy held that "all is number" (meaning whole numbers and their ratios). Legend says Hippasus of Metapontum was drowned at sea for revealing it. The legend is almost certainly fiction, but the shock was real: Greek mathematics afterwards treated geometric magnitudes and numbers as separate things for centuries.

22.5.5. Worked example 2: there are infinitely many primes

This proof, from Euclid’s Elements (around 300 BCE), is one of the oldest and most admired in mathematics.

Prime

A prime is an integer $p > 1$ whose only positive divisors are 1 and $p$. The first few are $2, 3, 5, 7, 11, 13$. An integer $n > 1$ that is not prime is composite. A fact we will prove by strong induction in Section 22.10: every integer $n > 1$ has at least one prime divisor.

Claim. There are infinitely many primes.

Proof. Suppose, for contradiction, that there are only finitely many primes, and list all of them: $p_1, p_2, \ldots, p_k$. Consider

\[N = p_1 p_2 \cdots p_k + 1.\]

$N > 1$, so $N$ has some prime divisor $p$. Since our list contains every prime, $p = p_i$ for some $i$. Then $p$ divides the product $p_1 p_2 \cdots p_k$, and $p$ divides $N$. So $p$ divides their difference:

\[N - p_1 p_2 \cdots p_k = 1.\]

But no prime divides 1 (primes are greater than 1). This is a contradiction, so the list could not have contained every prime: there are infinitely many. $\blacksquare$

Euclid’s N need not be prime

A very common misreading is "the product of the first $k$ primes, plus one, is always prime". The proof does not say that. It says $N$ has a prime factor not in the list. Indeed

$\quad 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509,$

which is composite, but its prime factors 59 and 509 are not among 2, 3, 5, 7, 11, 13, exactly as the proof predicts.

22.5.6. Alternative approaches: contradiction versus contrapositive

Every proof by contrapositive can be rewritten as a contradiction ("suppose $P$ and $\neg Q$; …; then $\neg P$; contradiction"). So which should you use?

If your argument goes cleanly from $\neg Q$ to $\neg P$, write it as a contrapositive. It is clearer, because every intermediate statement is actually true and can be reused.
Use contradiction when the statement is not naturally an implication ("$\sqrt 2$ is irrational", "there are infinitely many primes"), or when you need to use both $P$ and $\neg Q$ together.
Try a direct proof first when the hypothesis gives you something concrete to compute with.

Contradiction in type systems and solvers

SAT and SMT solvers (see Chapter 21) prove a property by contradiction: to show a formula $F$ always holds, they search for an assignment satisfying $\neg F$. If the search proves none exists ("UNSAT"), $F$ is valid. Tools like Microsoft’s Z3 are used in exactly this way to verify that compiler optimisations, cloud access policies or smart contracts cannot reach a bad state. In type theory, the "empty type" (Rust’s !, TypeScript’s never, Haskell’s Void) plays the role of a contradiction: a value of that type can never exist, so code that would have one is unreachable.

22.6. Proof by cases

22.6.1. The problem

Claim: for every integer $n$, $n^2 + n$ is even.

You cannot write $n = 2k$ (that assumes $n$ is even) or $n = 2k+1$ (that assumes $n$ is odd). But every integer is one or the other. So handle each separately.

22.6.2. The method

Example 115. Procedure — Proof by cases

Input: a claim $S$ about objects that fall into a known finite list of types.

Steps:

Choose cases $C_1, C_2, \ldots, C_m$ and justify that they are exhaustive (every object falls into at least one). They need not be exclusive, but usually are.
For each case $C_i$, assume $C_i$ and prove $S$.
Conclude that $S$ holds in all cases.

Output: a proof of $S$.

22.6.3. Worked example 1

Claim. For every integer $n$, $n^2 + n$ is even.

Proof. Every integer is even or odd.

Case 1: $n$ is even. Write $n = 2k$. Then

\[n^2 + n = 4k^2 + 2k = 2(2k^2 + k),\]

which is even.

Case 2: $n$ is odd. Write $n = 2k + 1$. Then

\[\begin{aligned} n^2 + n &= (4k^2 + 4k + 1) + (2k + 1) \\ &= 4k^2 + 6k + 2 \\ &= 2(2k^2 + 3k + 1), \end{aligned}\]

which is even. In both cases $n^2 + n$ is even. $\blacksquare$

22.6.4. Alternative approach

Factor first: $n^2 + n = n(n+1)$. Of two consecutive integers, one is even, and an even number times anything is even. This is shorter, but notice that "one of two consecutive integers is even" is itself a proof by cases, just hidden. When you find a factorisation like this, use it: it is clearer and generalises (the product of three consecutive integers is divisible by 3, for the same reason).

22.6.5. Worked example 2: last digits of squares

Claim. No perfect square ends in the digit 2, 3, 7 or 8.

Proof. The last digit of $n^2$ depends only on the last digit of $n$ (because $n = 10a + d$ gives $n^2 = 100a^2 + 20ad + d^2$, and the first two terms are multiples of 10). So there are ten cases, $d = 0, 1, \ldots, 9$:

$d$	0	1	2	3	4	5	6	7	8	9
$d^2$	0	1	4	9	16	25	36	49	64	81
last digit	0	1	4	9	6	5	6	9	4	1

The possible last digits are 0, 1, 4, 5, 6, 9. None is 2, 3, 7 or 8. $\blacksquare$

This is a perfectly rigorous proof even though it is just a table, because the ten cases are exhaustive. That is the key difference from "proof by example": here the examples provably cover everything.

Non-exhaustive cases

Proofs by cases fail silently when a case is missing. "Case $x > 0$ … Case $x < 0$ …" forgets $x = 0$. "Case $n$ prime … Case $n$ composite" forgets $n = 1$ (which is neither) and $n \le 0$. Before writing the cases, write the sentence that justifies exhaustiveness.

Cases and exhaustive pattern matching

A match statement in Rust, Swift, Scala or Haskell is a proof by cases, and the compiler checks the exhaustiveness condition for you: leave out a variant of an enum and you get an error. Python 3.10’s match does not enforce this, which is why a final case _: raise AssertionError arm is good practice. The bug class "forgot a case" (an unhandled state in a state machine, a missing else) is precisely the failure mode of a non-exhaustive proof.

A proof with 1,936 cases

The Four Colour Theorem (any map can be coloured with four colours so that neighbouring regions differ) was proved in 1976 by Kenneth Appel and Wolfgang Haken as a proof by cases: they reduced the problem to 1,936 configurations and checked them by computer. It was the first major theorem whose proof no human could check by hand, and it caused real controversy. In 2005 Georges Gonthier verified the whole proof in the Coq proof assistant, which settled most remaining doubts. You will meet graph colouring in Chapter 25.

22.7. Counterexamples

22.7.1. The problem

Is the following true? If $p$ is prime, then $2^p - 1$ is prime. Check: $2^2 - 1 = 3$, $2^3 - 1 = 7$, $2^5 - 1 = 31$, $2^7 - 1 = 127$. All prime. Should you try to prove it?

22.7.2. Intuition

Before investing in a proof, spend a few minutes trying to break the claim. Recall from Chapter 21 how a universal statement negates:

\[\neg\big(\forall x\; P(x)\big) \;\equiv\; \exists x\; \neg P(x).\]

"It is not true that every $x$ has property $P$" means "some $x$ lacks property $P$". So to disprove a "for all" claim you need exactly one counterexample: a specific object for which the claim fails. No general argument is needed.

Try the next prime: $p = 11$ gives $2^{11} - 1 = 2047 = 23 \times 89$. The claim is false. (Numbers of the form $2^p - 1$ that are prime are called Mersenne primes; the largest known primes are of this form.)

22.7.3. The method

Example 116. Procedure — Hunting for a counterexample

Input: a universal claim "for all $x$ in $D$, $P(x)$".

Steps:

Try the edge cases first: 0, 1, negative numbers, the smallest allowed value, equal inputs, the empty set or empty list.
Try special values: 2 (the only even prime), perfect squares, numbers just below powers of ten, fractions between 0 and 1 (where squaring makes things smaller).
If those pass, search systematically, by hand or with a short program.
If you find $x_0$ with $\neg P(x_0)$, verify it carefully and state it: "The claim is false: take $x = x_0$; then …".
If a long search finds nothing, that is evidence (not proof) that the claim is true. Ask why it keeps working; the reason is often the proof.

Output: a counterexample, or a well-founded belief that it is time to attempt a proof.

22.7.4. Worked example

Claim. For all real $x$, $x^2 \ge x$.

Edge cases: $x = 0$ gives $0 \ge 0$, true. $x = 1$ gives $1 \ge 1$, true. $x = -3$ gives $9 \ge -3$, true. Special values: a fraction between 0 and 1. $x = \tfrac12$ gives $\tfrac14 \ge \tfrac12$, false.

Disproof. The claim is false: for $x = \tfrac12$, $x^2 = \tfrac14 < \tfrac12 = x$. $\blacksquare$

One clean counterexample is the whole disproof. You do not need to describe all the failures (here, every $x$ with $0 < x < 1$), though doing so can be illuminating.

Counterexamples to existence claims, and to implications

An existence claim ("there is an $x$ with $P(x)$") cannot be disproved by a counterexample. Its negation is "for all $x$, not $P(x)$", which needs a general proof.
A counterexample to "if $P(x)$ then $Q(x)$" must satisfy $P$ and fail $Q$. An $x$ for which $P$ is false is not a counterexample: the implication is vacuously true there (see Chapter 21).

Euler wrong again

In 1769 Euler conjectured that you need at least $k$ $k$-th powers to sum to another $k$-th power (generalising Fermat’s Last Theorem). It stood for nearly two centuries, until in 1966 L. J. Lander and T. R. Parkin found, by computer search, a counterexample whose paper is one of the shortest ever published:

$\quad 27^5 + 84^5 + 110^5 + 133^5 = 144^5.$

Four fifth powers summing to a fifth power. One line disproved a conjecture by one of history’s greatest mathematicians.

Counterexample hunter

Type a claim as a Python predicate (for example lambda n: is_prime(n*n + n + 41) or lambda p: not is_prime(p) or is_prime(2**p - 1)) and a search range. The lab tests every value, plots passes and failures like the Euler-polynomial chart above, and highlights the first counterexample. Try to guess, before running, how far each claim survives.

Try it: Hunt counterexamples in Python

22.7.5. Where you’d use this

Contradiction, on your desk. A4 paper is designed so that halving a sheet gives the same shape, which forces the ratio of the sides to be $\sqrt 2$. Because $\sqrt 2$ is irrational, no sheet with whole-millimetre sides can have exactly that ratio. The standard picks 210 mm by 297 mm, and $297/210 = 1.41428\ldots$ against $\sqrt 2 = 1.41421\ldots$: off by about 0.005%, which is the best the proof allows at that precision.

Cases, as a quick check. The last-digit table proves that a number ending in 2, 3, 7 or 8 cannot be a perfect square. So 7,423,898 is not a square, with no square root needed. Fast perfect-square tests in big-number libraries use the same idea with remainders mod 64 or mod 256 (there are only 44 possible remainders mod 256 for squares, out of 256) to reject most non-squares before computing anything expensive.

Infinitely many primes, in your browser. Every HTTPS connection that uses RSA relies on a fresh supply of large primes; Euclid’s proof guarantees the supply never runs out, and the prime number theorem (Chapter 23) says how dense it is: about one in $\ln 2^{1024} \approx 710$ numbers near $2^{1024}$ is prime.

Counterexamples, at work. A single failing case refutes a universal claim, so a bug report with one reproducible input is worth more than a hundred "works for me" reports. Medicine works the same way: one well-documented serious reaction is enough to withdraw the claim that a drug is safe for everyone.

22.8. Exercises: direct, contrapositive, contradiction, cases

Recognition. For each claim, name the technique you would try first and say why: (a) If $a \mid b$ then $a \mid 3b$. (b) If $n^2$ is odd then $n$ is odd. (c) $\sqrt 3$ is irrational. (d) For every integer $n$, $n^3 - n$ is divisible by 3. (e) Every prime is odd.
Application. Prove that the product of two odd integers is odd.
Application. Prove: if $n^2$ is odd then $n$ is odd.
Application. Prove that $n^3 - n$ is divisible by 3 for every integer $n$.
Problem solving. Prove that $\sqrt 3$ is irrational. (You will first need a lemma: if $3 \mid p^2$ then $3 \mid p$. Prove it by contrapositive, with cases.)
Problem solving. Disprove: "for integers $a, b, c$ with $a \ne 0$, if $a \mid bc$ then $a \mid b$ or $a \mid c$."
Problem solving. Prove that there is no largest even integer.

Answers

(a) Direct: $b = ak$ so $3b = a(3k)$. (b) Contrapositive: "if $n$ even then $n^2$ even" is easy to compute. (c) Contradiction: the statement is a negative ("not a fraction"). (d) Cases on the remainder of $n$ modulo 3, or factor $n^3 - n = (n-1)n(n+1)$. (e) It is false: look for a counterexample ($2$).
Let $a = 2j + 1$, $b = 2k + 1$. Then $ab = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1$, which is odd.
Contrapositive: if $n$ is even, $n = 2k$, then $n^2 = 4k^2 = 2(2k^2)$ is even. So if $n^2$ is odd, $n$ is odd.
$n^3 - n = n(n^2 - 1) = (n-1)n(n+1)$, a product of three consecutive integers. Every integer leaves remainder 0, 1 or 2 when divided by 3. If $n = 3k$, then $3 \mid n$. If $n = 3k + 1$, then $n - 1 = 3k$. If $n = 3k + 2$, then $n + 1 = 3k + 3 = 3(k+1)$. In every case one factor is divisible by 3, so the product is.
Lemma (contrapositive): if $3 \nmid p$ then $3 \nmid p^2$. If $3 \nmid p$, then $p = 3m + 1$ or $p = 3m + 2$. Case 1: $p^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1$. Case 2: $p^2 = 9m^2 + 12m + 4 = 3(3m^2 + 4m + 1) + 1$. Either way $p^2$ leaves remainder 1, so $3 \nmid p^2$. Main proof: suppose $\sqrt 3 = p/q$ in lowest terms. Then $3q^2 = p^2$, so $3 \mid p^2$, so $3 \mid p$ by the lemma. Write $p = 3r$: $3q^2 = 9r^2$, so $q^2 = 3r^2$, so $3 \mid q^2$ and $3 \mid q$. Then 3 divides both $p$ and $q$, contradicting lowest terms.
Take $a = 4$, $b = 2$, $c = 2$. Then $bc = 4$ and $4 \mid 4$, but $4 \nmid 2$. (The statement is true when $a$ is prime; that is Euclid’s lemma, see Chapter 23.)
Suppose, for contradiction, that $M$ is the largest even integer. Then $M = 2k$, and $M + 2 = 2(k + 1)$ is even and larger than $M$. Contradiction.

22.9. Mathematical induction

22.9.1. The problem

Here are some sums of odd numbers:

\[1 = 1, \quad 1 + 3 = 4, \quad 1 + 3 + 5 = 9, \quad 1 + 3 + 5 + 7 = 16.\]

They are the perfect squares. It seems that the sum of the first $n$ odd numbers is $n^2$. We have learned to distrust patterns, so we need a proof for every $n$. A direct algebraic manipulation is not obvious. But there is something we can say: if the pattern holds up to some $n = k$, then adding the next odd number, $2k + 1$, gives $k^2 + 2k + 1 = (k + 1)^2$. So the pattern propagates: each case hands its truth to the next.

That idea, made precise, is mathematical induction.

22.9.2. Intuition: dominoes

Imagine an infinite row of dominoes, one for each natural number. Two facts guarantee they all fall:

The first domino is pushed over. (Base case.)
Whenever any domino falls, it knocks over the next one. (Inductive step.)

You do not need to watch each domino. Fact 2 is a single statement about a general domino $k$; together with fact 1 it reaches every domino in the row.

A row of dominoes labelled P(1), P(2), …; the first three falling, with annotations for base case and inductive step

Figure 200. Induction as falling dominoes: the base case starts the chain, and the inductive step makes each domino knock over the next.

Both facts are essential. Without the base case, every domino would knock over its neighbour, but nothing starts the chain. Without the inductive step, the first domino falls and nothing follows.

22.9.3. Vocabulary and notation

Sigma notation

The symbol $\Sigma$ (capital Greek sigma, for "sum") abbreviates long sums:

\[\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n.\]

Read it as "the sum, for $i$ from 1 to $n$, of $a_i$". The index $i$ is a dummy variable (like a loop variable: it has no meaning outside the sum), the numbers below and above $\Sigma$ are its starting and ending values, and $a_i$ is the term, an expression in $i$. For example $\sum_{i=1}^{4} (2i - 1) = 1 + 3 + 5 + 7 = 16$. In Python: sum(2*i - 1 for i in range(1, n + 1)). A key identity for induction is "peel off the last term":

\[\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^{k} a_i\right) + a_{k+1}.\]

Sigma notation is covered in more depth in Chapter 14.

Induction vocabulary

$P(n)$ denotes a statement depending on $n$, true or false for each $n$; for example $P(n)$: "$\sum_{i=1}^n (2i-1) = n^2$". It is a predicate, not a number.
The base case is the proof of $P(n_0)$ for the starting value $n_0$ (often 0 or 1).
The inductive hypothesis (IH) is the assumption "$P(k)$ is true" for an arbitrary $k \ge n_0$.
The inductive step is the proof that $P(k) \Rightarrow P(k+1)$ for every $k \ge n_0$.
The principle of mathematical induction: if $P(n_0)$ is true and $P(k) \Rightarrow P(k+1)$ for all $k \ge n_0$, then $P(n)$ is true for all integers $n \ge n_0$.

22.9.4. Why it works

Why is induction a valid proof technique, and not just a nice story about dominoes? Suppose the base case and inductive step are proved, but $P(n)$ is false for some $n \ge n_0$. Among all the $n$ for which $P(n)$ fails, there is a smallest one; call it $m$. (Every non-empty set of natural numbers has a least element. This is the well-ordering principle, an axiom of the natural numbers.) $m \ne n_0$, because the base case holds. So $m - 1 \ge n_0$, and $P(m - 1)$ is true, because $m$ was the smallest failure. But then the inductive step, with $k = m - 1$, gives $P(m)$. Contradiction. So there is no failure.

In other words: induction is a packaged proof by contradiction about the "first bad case". That viewpoint is often useful when you are stuck: ask "what would the smallest counterexample look like?"

22.9.5. The method

Example 117. Procedure — Proof by (ordinary) induction

Input: a claim "for all integers $n \ge n_0$, $P(n)$".

Steps:

State $P(n)$ explicitly as a sentence or equation.
Base case. Verify $P(n_0)$ by direct computation. Show both sides.
Inductive hypothesis. Write "Let $k \ge n_0$ and assume $P(k)$." Write out $P(k)$ in full.
Target. Write out $P(k+1)$ in full by substituting $k+1$ for $n$. Simplify the target if helpful.
Inductive step. Starting from one side of $P(k+1)$, find $P(k)$ inside it (for sums: peel off the last term), apply the IH, and simplify until you reach the other side. Label the line where the IH is used.
Conclude: "By induction, $P(n)$ holds for all $n \ge n_0$."

Output: a proof for every $n \ge n_0$.

22.9.6. Worked example 1: the sum of the first $n$ odd numbers

Claim. For all integers $n \ge 1$, $\displaystyle\sum_{i=1}^{n} (2i - 1) = n^2$.

Step 1. $P(n)$: $1 + 3 + \cdots + (2n - 1) = n^2$.

Step 2: base case $n = 1$. Left side: $\sum_{i=1}^{1}(2i-1) = 2(1) - 1 = 1$. Right side: $1^2 = 1$. Equal, so $P(1)$ holds.

Step 3: inductive hypothesis. Let $k \ge 1$ and assume

\[\sum_{i=1}^{k} (2i - 1) = k^2.\]

Step 4: target. We must show $\sum_{i=1}^{k+1} (2i - 1) = (k+1)^2$.

Step 5: inductive step.

\[\begin{aligned} \sum_{i=1}^{k+1} (2i - 1) &= \left(\sum_{i=1}^{k} (2i - 1)\right) + \big(2(k+1) - 1\big) \qquad\text{(peel off the last term)} \\ &= k^2 + \big(2(k+1) - 1\big) \qquad\text{(by the IH)} \\ &= k^2 + 2k + 1 \qquad\text{(simplify)} \\ &= (k+1)^2. \qquad\text{(factor the perfect square)} \end{aligned}\]

Step 6. By induction, $\sum_{i=1}^{n}(2i - 1) = n^2$ for every $n \ge 1$. $\blacksquare$

The inductive step has a picture. A $k \times k$ square of dots grows into a $(k+1) \times (k+1)$ square by adding an L-shaped border of $k$ dots along the top, $k$ down the side and one in the corner: $2k + 1$ dots, the next odd number.

A 5 by 5 grid of squares colored in nested L-shaped layers of 1, 3, 5, 7 and 9 squares from the bottom-left corner outward

Figure 201. The sum of the first five odd numbers is $5^2$: each odd number is an L-shaped layer wrapped around the previous square

22.9.7. Worked example 2: the sum of squares

Claim. For all $n \ge 1$,

\[\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}.\]

Base case $n = 1$. Left: $1^2 = 1$. Right: $\frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1$. Equal.

Inductive hypothesis. Assume $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$ for some $k \ge 1$.

Target. Substitute $n = k + 1$ into the right-hand side:

\[\frac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}.\]

Inductive step.

\[\begin{aligned} \sum_{i=1}^{k+1} i^2 &= \sum_{i=1}^{k} i^2 + (k+1)^2 \qquad\text{(peel off the last term)} \\ &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \qquad\text{(by the IH)} \\ &= \frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6} \qquad\text{(common denominator)} \\ &= \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} \qquad\text{(factor out } k+1\text{)} \\ &= \frac{(k+1)\big[2k^2 + k + 6k + 6\big]}{6} \qquad\text{(expand inside the bracket)} \\ &= \frac{(k+1)(2k^2 + 7k + 6)}{6} \qquad\text{(collect like terms)} \\ &= \frac{(k+1)(k+2)(2k+3)}{6}. \qquad\text{(factor: } (k+2)(2k+3) = 2k^2 + 7k + 6\text{)} \end{aligned}\]

That is the target, so by induction the formula holds for all $n \ge 1$. $\blacksquare$

The tactical lesson: factor out the common piece early (here $k+1$) instead of expanding everything into a cubic. You know what the target looks like, so steer towards it.

22.9.8. Worked example 3: an inequality

Induction is not just for equations.

Claim. $2^n > n^2$ for all integers $n \ge 5$.

Why start at 5? Check small values: $2^1 = 2 > 1$, $2^2 = 4 = 4$ (not greater), $2^3 = 8 < 9$, $2^4 = 16 = 16$, $2^5 = 32 > 25$. The claim is false for $n = 2, 3, 4$, so the base case must be $n_0 = 5$.

Base case $n = 5$: $2^5 = 32 > 25 = 5^2$. True.

Inductive hypothesis. Assume $2^k > k^2$ for some $k \ge 5$.

Target. $2^{k+1} > (k+1)^2$.

Inductive step. With inequalities, the trick is to bridge from what the IH gives you to what the target needs:

\[\begin{aligned} 2^{k+1} &= 2 \cdot 2^k \\ &> 2k^2 \qquad\text{(by the IH, multiplied by 2)}. \end{aligned}\]

Now it suffices to show $2k^2 \ge (k+1)^2$, i.e., $2k^2 \ge k^2 + 2k + 1$, i.e., $k^2 - 2k - 1 \ge 0$. Complete the square: $k^2 - 2k - 1 = (k-1)^2 - 2$. For $k \ge 5$, $(k - 1)^2 \ge 16$, so $(k-1)^2 - 2 \ge 14 > 0$. Therefore

\[2^{k+1} > 2k^2 \ge (k+1)^2,\]

which gives $2^{k+1} > (k+1)^2$. By induction, $2^n > n^2$ for all $n \ge 5$. $\blacksquare$

22.9.9. Worked example 4: divisibility

Claim. $3 \mid 4^n - 1$ for all $n \ge 0$.

Base case $n = 0$: $4^0 - 1 = 0 = 3 \cdot 0$, divisible by 3.

Inductive hypothesis. Assume $4^k - 1 = 3m$ for some integer $m$.

Inductive step. The trick is to make $4^k - 1$ appear inside $4^{k+1} - 1$:

\[\begin{aligned} 4^{k+1} - 1 &= 4 \cdot 4^k - 1 \\ &= 4 \cdot 4^k - 4 + 3 \qquad\text{(subtract and add 3)} \\ &= 4(4^k - 1) + 3 \qquad\text{(factor 4 from the first two terms)} \\ &= 4(3m) + 3 \qquad\text{(by the IH)} \\ &= 3(4m + 1). \end{aligned}\]

So $3 \mid 4^{k+1} - 1$. By induction the claim holds for all $n \ge 0$. $\blacksquare$

(Chapter 23 gives a one-line alternative: $4 \equiv 1 \pmod 3$, so $4^n \equiv 1^n = 1$.)

22.9.10. Alternative approaches and choosing a method

Induction verifies a formula; it does not discover it. To prove $\sum i^2 = n(n+1)(2n+1)/6$ you must already know the right-hand side. So the realistic workflow is:

Discover the formula: compute small cases, guess a pattern, or derive it (pairing, as Gauss did; telescoping sums; fitting a polynomial of the right degree to the first few values).
Check it numerically for many $n$ (a quick script).
Prove it, usually by induction.

When a direct derivation exists (the Gauss pairing for $\sum i$, the geometric series formula derived in Chapter 14), it is often more illuminating than induction because it explains why. Induction is the reliable fallback that works when you have the answer but not the insight, and it is the natural tool whenever the objects are defined step by step (recurrences, recursive functions, data structures).

Forgetting the base case

"Claim: $n = n + 1$ for all $n$. Inductive step: assume $k = k + 1$. Adding 1 to both sides, $k + 1 = k + 2$. So $P(k) \Rightarrow P(k+1)$." The inductive step is valid. The claim is absurd. What is missing is the base case: $0 = 1$ is false, so no domino is ever pushed. Always prove the base case, even when it looks trivial.

Assuming what you want to prove

The inductive hypothesis is "assume $P(k)$ for one arbitrary $k$", not "assume $P(n)$ for all $n$", which would be assuming the theorem. If your write-up says "assume the formula is true for all $n$", it is circular.

22.9.11. Where you’d use this

Games: a winning strategy is an induction proof. Twenty coins are on the table. Players take turns removing 1, 2 or 3 coins, and whoever takes the last coin wins. Claim: the player to move loses exactly when the number of coins is a multiple of 4. With 0 coins the player to move has already lost. If the count is a multiple of 4, any move leaves a non-multiple; if it is not, you can take 1, 2 or 3 to leave a multiple of 4. By (strong) induction the claim holds for every count, so with 20 coins you should let your opponent go first and then always make each round total 4.

Finance: why the compound-interest formula is right. If a balance starts at $B_0 = P$ and each year $B_{k+1} = B_k(1 + r)$, induction proves $B_n = P(1 + r)^n$ for every $n$: the base case is $B_0 = P$, and the step is $B_{k+1} = P(1 + r)^k (1 + r) = P(1 + r)^{k+1}$. So $1,000 at 5% for 3 years becomes $1000 \times 1.05^3 = 1157.63$, and the formula, not a spreadsheet of 30 rows, is what you trust for a 30-year mortgage.

Medicine: drug accumulation. A patient takes 100 mg of a drug once every half-life, so half of what is in the body is cleared between doses. Just after the $n$-th dose the amount is $100(1 + \tfrac12 + \cdots + \tfrac1{2^{n-1}})$, which induction shows equals $200(1 - 2^{-n})$ mg. After 5 doses that is $200 \times \tfrac{31}{32} = 193.75$ mg, and the level never exceeds 200 mg however long treatment continues. Pharmacologists use exactly this "steady state" rule of thumb (about five half-lives to get within a few percent).

Computing. Every recursive function and every divide-and-conquer running time (merge sort’s $T(n) = 2T(n/2) + n$ gives $n \log_2 n$ comparisons, roughly) is justified by induction; Section 22.11 makes the link explicit.

Proof by induction, checked by a script

An "induction workbench": enter a conjectured closed form such as n*(n+1)(2*n+1)//6 and a recursive definition such as S(n) = S(n-1) + n*2. The lab tabulates both for $n = 1 \ldots 50$ (discovery and checking), then animates the dominoes: the base-case domino turns green when you confirm $P(n_0)$, and the chain falls only after you enter the algebra of the inductive step.

Induction everywhere

The first clear use of induction is usually credited to Francesco Maurolico (1575) and Blaise Pascal, who used it around 1654 in his work on the arithmetic triangle. The name "mathematical induction" came much later, from Augustus De Morgan in 1838. It is unrelated to inductive reasoning in science (generalising from observations), which is exactly the kind of reasoning the Euler polynomial warns against. Mathematical induction is fully deductive.

US curriculum

Induction appears in some Algebra II or Precalculus courses (often with sequences and series) and occasionally in honors high-school classes, but most US students meet it properly in college Discrete Mathematics. The AP Calculus syllabi do not include it. A student comfortable with algebraic manipulation from Algebra I–II has everything needed.

22.10. Strong induction

22.10.1. The problem

Claim: every integer $n \ge 2$ is a product of one or more primes. (A prime by itself counts as a product of one prime.)

Try ordinary induction. Assume $k$ is a product of primes; show $k + 1$ is. But $k$ and $k + 1$ have no useful relationship here: knowing $14 = 2 \cdot 7$ tells you nothing about 15. What does help: if $k + 1$ is composite, say $k + 1 = ab$, then $a$ and $b$ are smaller numbers, and we would like to know they are products of primes. We need the hypothesis for all smaller numbers, not just the one immediately before.

22.10.2. Intuition

Strong induction (also called complete induction) lets the inductive step use every earlier case:

\[\big(P(n_0) \land P(n_0 + 1) \land \cdots \land P(k)\big) \Rightarrow P(k+1).\]

In domino terms: each domino is knocked over by the combined weight of all the dominoes before it. It is no more powerful than ordinary induction (you can convert one to the other by using the statement "$P$ holds for all values up to $n$"), but it is far more convenient whenever $P(k+1)$ depends on cases further back.

Figure 202. Ordinary induction uses only P(k) to reach P(k + 1); strong induction may use all of P(1), …, P(k).

22.10.3. The method

Example 118. Procedure — Proof by strong induction

Input: a claim "for all integers $n \ge n_0$, $P(n)$".

Steps:

Base case(s). Prove $P(n_0)$, and as many further cases as the inductive step needs (if the step reaches back $j$ places, prove $j$ base cases).
Strong inductive hypothesis. Let $k$ be at least the last base case and assume $P(i)$ for all $i$ with $n_0 \le i \le k$.
Inductive step. Prove $P(k+1)$, using any of the $P(i)$ that you need. Check that every $i$ you use is in the range $n_0 \le i \le k$.
Conclude by strong induction.

Output: a proof for all $n \ge n_0$.

22.10.4. Worked example 1: every integer $n \ge 2$ is a product of primes

Base case $n = 2$: 2 is prime, so it is a product of one prime.

Strong IH. Let $k \ge 2$ and assume every integer $i$ with $2 \le i \le k$ is a product of primes.

Inductive step. Consider $k + 1$. There are two cases.

Case 1: $k+1$ is prime. Then it is a product of one prime. Done.

Case 2: $k+1$ is composite. Then $k + 1 = ab$ for integers with $2 \le a, b \le k$. (Composite means it has a divisor $a$ other than 1 and itself; then $b = (k+1)/a$ is also strictly between 1 and $k+1$.) By the strong IH, $a = p_1 \cdots p_r$ and $b = q_1 \cdots q_s$ are products of primes. So $k + 1 = p_1 \cdots p_r \, q_1 \cdots q_s$ is a product of primes.

By strong induction, every integer $n \ge 2$ is a product of primes. $\blacksquare$

In particular every $n \ge 2$ has at least one prime divisor, which is the fact Euclid’s proof used. This is the existence half of the Fundamental Theorem of Arithmetic; uniqueness of the factorisation is proved in Chapter 23.

22.10.5. Worked example 2: postage stamps

Claim. Every amount of postage of 12 cents or more can be made using only 4-cent and 5-cent stamps.

Here $P(n)$: "there are non-negative integers $a, b$ with $n = 4a + 5b$".

The idea: if we can make $n - 4$ cents, add one 4-cent stamp to make $n$. That reaches back four places, so we need four base cases.

Base cases.

\[\begin{aligned} 12 &= 4 \cdot 3 + 5 \cdot 0 \\ 13 &= 4 \cdot 2 + 5 \cdot 1 \\ 14 &= 4 \cdot 1 + 5 \cdot 2 \\ 15 &= 4 \cdot 0 + 5 \cdot 3 \end{aligned}\]

Strong IH. Let $k \ge 15$ and assume $P(i)$ for all $12 \le i \le k$.

Inductive step. Since $k \ge 15$, $k + 1 \ge 16$, so $12 \le (k+1) - 4 \le k$. By the IH, $(k + 1) - 4 = 4a + 5b$. Then $k + 1 = 4(a + 1) + 5b$. Done. $\blacksquare$

Why 12? Because 11 cannot be made (11 is not of the form $4a + 5b$: try $b = 0, 1, 2$, giving remainders 11, 6, 1, none a multiple of 4). This is the Frobenius coin problem; for two coin values $x, y$ with no common factor the largest unpayable amount is $xy - x - y = 20 - 4 - 5 = 11$.

22.10.6. Worked example 3: a bound on Fibonacci numbers

The Fibonacci numbers are defined by $F_1 = 1$, $F_2 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \ge 3$: $1, 1, 2, 3, 5, 8, 13, \ldots$

Claim. $F_n < 2^n$ for all $n \ge 1$.

The recurrence reaches back two places, so two base cases. $F_1 = 1 < 2 = 2^1$ and $F_2 = 1 < 4 = 2^2$.

Strong IH. Let $k \ge 2$, and assume $F_i < 2^i$ for all $1 \le i \le k$.

Inductive step.

\[\begin{aligned} F_{k+1} &= F_k + F_{k-1} \qquad\text{(definition, valid since } k + 1 \ge 3\text{)} \\ &< 2^k + 2^{k-1} \qquad\text{(IH for } i = k \text{ and } i = k-1\text{, both in } [1, k]\text{)} \\ &< 2^k + 2^k \qquad\text{(since } 2^{k-1} < 2^k\text{)} \\ &= 2^{k+1}. \end{aligned}\]

$\blacksquare$

Too few base cases

If the inductive step for $P(k+1)$ uses $P(k-1)$, then with only one base case $P(1)$ the step for $k + 1 = 2$ would need $P(0)$, which you never proved (and $F_0$ may not even be defined). The rule: if the step reaches back $j$ places, you need $j$ consecutive base cases. Check the smallest $k$ for which you invoke the step and make sure everything it uses is covered.

22.11. Structural induction and recursion

22.11.1. The problem

Programmers rarely work with "for all integers $n$". They work with lists, trees, expressions and JSON documents. How do you prove something about every binary tree, or every well-formed expression?

22.11.2. Intuition

These objects are defined recursively: a list is either empty or an element followed by a list. A full binary tree is either a single leaf, or a root node with two full binary subtrees. Every object is built from smaller objects of the same kind, and the building process starts from base objects.

Structural induction follows the definition:

Base case: prove the property for each base object (empty list, single leaf).
Inductive step: for each way of building a bigger object from smaller ones, assume the property for the smaller pieces and prove it for the result.

This is ordinary strong induction in disguise (induct on the size of the object), but it is much more natural to write.

Recursive definition, full binary tree

A recursive definition (or inductive definition) defines a set of objects by (1) some base objects and (2) rules that build new objects from existing ones, with nothing else included.
A full binary tree is defined by: (base) a single node is a full binary tree; (rule) if $T_1$ and $T_2$ are full binary trees, then a new root node with left subtree $T_1$ and right subtree $T_2$ is a full binary tree. In a full binary tree every node has 0 or 2 children. A node with 0 children is a leaf; one with 2 is an internal node.

22.11.3. Worked example: leaves versus internal nodes

Claim. In every full binary tree, the number of leaves $L$ equals the number of internal nodes $I$ plus one: $L = I + 1$.

Base case. A single node is a leaf and has no children: $L = 1$, $I = 0$, and $1 = 0 + 1$.

Inductive step. Let $T$ be built from a new root with subtrees $T_1$ and $T_2$, and assume (structural IH) that $L_1 = I_1 + 1$ and $L_2 = I_2 + 1$. The leaves of $T$ are exactly the leaves of $T_1$ and $T_2$ (the root is not a leaf). The internal nodes of $T$ are those of $T_1$ and $T_2$ plus the root. So

\[\begin{aligned} L &= L_1 + L_2 \\ &= (I_1 + 1) + (I_2 + 1) \qquad\text{(by the structural IH)} \\ &= (I_1 + I_2 + 1) + 1 \\ &= I + 1. \qquad\text{(since } I = I_1 + I_2 + 1\text{)} \end{aligned}\]

By structural induction, $L = I + 1$ for every full binary tree. $\blacksquare$

Application: a knockout tournament is a full binary tree whose leaves are the $L$ players and whose internal nodes are the matches. So a tournament with 64 players has exactly 63 matches, regardless of how the bracket is arranged. Another: a Huffman code tree (used in compression formats such as DEFLATE) with $L$ symbols has $L - 1$ merge steps.

22.11.4. Induction and recursion are the same idea

Compare a recursive function with an induction proof:

def sum_to(n):
    """1 + 2 + ... + n, defined recursively."""
    if n == 1:                 # base case
        return 1
    return sum_to(n - 1) + n   # "inductive step": trust sum_to(n-1)

assert all(sum_to(n) == n * (n + 1) // 2 for n in range(1, 500))
print(sum_to(100))

To convince yourself sum_to is correct you reason exactly by induction: it is correct for $n = 1$ (base case); and if sum_to(n - 1) returns $(n-1)n/2$ (inductive hypothesis), then sum_to(n) returns

\[\frac{(n-1)n}{2} + n = \frac{(n-1)n + 2n}{2} = \frac{n(n+1)}{2}.\]

The assert line is a test, valuable but not a proof. The algebra is the proof.

The recursive leap of faith

Teachers of recursion tell students to take the "recursive leap of faith": when writing f(n), assume f already works on smaller inputs and concentrate on combining the results. That leap is not faith at all; it is the inductive hypothesis, and the reasoning is valid exactly when (1) the base cases are correct and (2) every recursive call is on a strictly smaller input that eventually reaches a base case. Condition (2) is the structural-induction version of "the dominoes are in a line": it is what makes the recursion terminate. Functional languages (Haskell, OCaml, and especially proof-oriented ones like Lean and Agda) make the correspondence explicit: a function defined by structural recursion over an algebraic data type is a proof by structural induction.

Recursion tree and proof tree

Build a full binary tree by clicking leaves to split them. The lab keeps live counts of leaves and internal nodes (watch $L - I$ stay at 1), and shows the structural-induction proof annotating each split: "this split turns one leaf into an internal node and adds two leaves: $L$ goes up by 1, $I$ goes up by 1".

22.12. Exercises: induction

Recognition. In the proof that $F_n < 2^n$, why are two base cases needed? What would go wrong with only $F_1 < 2$?
Application. Prove by induction that $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ for all $n \ge 1$.
Application. Prove that $\displaystyle\sum_{i=0}^{n-1} 2^i = 2^n - 1$ for all $n \ge 1$. (Interpret this in binary.)
Application. Prove that $n! > 2^n$ for all $n \ge 4$. ($n! = 1 \cdot 2 \cdots n$, "$n$ factorial".)
Problem solving. Prove by induction that $6 \mid n^3 - n$ for all $n \ge 0$. (Use the result of Section 22.6.)
Problem solving. Prove that every integer $n \ge 8$ can be written as $3a + 5b$ with non-negative integers $a, b$.
Problem solving. A perfect binary tree of height $h$ is a single node if $h = 0$, and otherwise a root with two perfect subtrees of height $h - 1$. Prove it has $2^{h+1} - 1$ nodes.

Answers

The step proves $P(k+1)$ from $P(k)$ and $P(k-1)$, and is first used at $k + 1 = 3$, which needs $P(2)$ and $P(1)$. With only $P(1)$ proved, the step for $k+1 = 2$ would need $P(0)$, and the recurrence $F_2 = F_1 + F_0$ is not part of the definition. Without $P(2)$ the chain never starts.
Base: $1 = 1 \cdot 2 / 2$. Step: $\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$.
Base $n = 1$: $2^0 = 1 = 2^1 - 1$. Step: $\sum_{i=0}^{k} 2^i = (2^k - 1) + 2^k = 2 \cdot 2^k - 1 = 2^{k+1} - 1$. In binary, $111\ldots1$ ($n$ ones) plus 1 is $1000\ldots0$ (a 1 followed by $n$ zeros), which is $2^n$. This is why the largest unsigned $n$-bit integer is $2^n - 1$.
Base $n = 4$: $4! = 24 > 16 = 2^4$. Step: assume $k! > 2^k$ with $k \ge 4$. Then $(k+1)! = (k+1)\,k! > (k+1)\,2^k \ge 2 \cdot 2^k = 2^{k+1}$, using $k + 1 \ge 2$.
Base $n = 0$: $0 - 0 = 0 = 6 \cdot 0$. Step: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k(k+1)$. By the IH, $6 \mid k^3 - k$. By Section 22.6, $k(k+1)$ is even, so $k(k+1) = 2t$ and $3k(k+1) = 6t$. A sum of two multiples of 6 is a multiple of 6.
Strong induction with three base cases: $8 = 3 + 5$, $9 = 3 \cdot 3$, $10 = 5 \cdot 2$. For $k \ge 10$, $k + 1 \ge 11$, so $8 \le (k+1) - 3 \le k$; by the IH $(k+1) - 3 = 3a + 5b$, hence $k + 1 = 3(a+1) + 5b$.
Structural induction on $h$. Base $h = 0$: one node, and $2^1 - 1 = 1$. Step: a tree of height $h + 1$ is a root plus two perfect trees of height $h$, each with $2^{h+1} - 1$ nodes by the IH. Total: $1 + 2(2^{h+1} - 1) = 2^{h+2} - 1 = 2^{(h+1)+1} - 1$.

22.13. Proving programs correct: loop invariants

22.13.1. The problem

Binary search is ten lines long and notoriously easy to get wrong: off-by-one errors in lo, hi and mid, infinite loops, wrong results on empty arrays. Jon Bentley reported that when he set it as an exercise for professional programmers, around 90% of their solutions contained a bug. Tests catch some of these errors. How do we know a correct version is correct?

22.13.2. Intuition

A loop is induction in disguise. Each iteration is an inductive step; the state before the first iteration is the base case. The statement being proved is a loop invariant: a condition on the program’s variables that is true before the loop starts and stays true after every iteration. When the loop stops, the invariant plus the stopping condition should give you exactly what you wanted.

Loop invariant, variant, pre- and postcondition

A precondition is what must be true when a piece of code starts (e.g., "`a` is sorted").
A postcondition is what the code guarantees when it ends (e.g., "the return value is an index of target, or -1 if target is absent").
A loop invariant is a statement about the variables that holds every time execution reaches the top of the loop (before the test).
A loop variant (or ranking function, or termination measure) is an integer quantity that is always non-negative while the loop runs and strictly decreases with every iteration. Its existence proves the loop terminates.
A program is partially correct if, whenever it terminates, the postcondition holds; totally correct if, in addition, it always terminates.

22.13.3. The method

Example 119. Procedure — Proving a loop correct

Input: a loop, its precondition, and the desired postcondition.

Steps:

Choose an invariant $I$: typically "the work done so far is correct" or "the answer, if it exists, is still in the region we have not excluded". A good invariant mentions every variable the loop changes.
Initialisation (base case). Show $I$ holds just before the first iteration, using the precondition and the initial assignments.
Maintenance (inductive step). Assume $I$ holds at the top of an iteration and the loop condition is true. Show $I$ holds again after the body runs. Do this for every branch of the body.
Termination. Exhibit a variant: a non-negative integer that strictly decreases on every iteration. Then the loop must stop.
Exit (conclusion). Show that $I$ together with the negation of the loop condition implies the postcondition. Also check any early return.

Output: a proof of total correctness.

22.13.4. Worked example: binary search

def binary_search(a, target):
    """Return an index i with a[i] == target, or -1. `a` must be sorted."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        # Invariant: if target is in a, then it is in a[lo..hi].
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1      # a[0..mid] are all < target: discard them
        else:
            hi = mid - 1      # a[mid..] are all > target: discard them
    return -1                 # a[lo..hi] is empty, so target is not in a

a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(a, 23), binary_search(a, 7))

5 -1

Here a[lo..hi] means the elements with indices from lo to hi inclusive; it is empty when lo > hi.

Precondition: a is sorted in non-decreasing order. Postcondition: the result r satisfies a[r] == target, or r == -1 and target does not occur in a.

Sorted array with indices 0 to 9; grey regions outside lo=3 and hi=7 labelled all less than target and all greater than target

Figure 203. The binary-search invariant: everything to the left of lo is smaller than the target and everything to the right of hi is larger, so if the target is anywhere, it is between lo and hi.

Step 1: invariant. $I$: "if target occurs in a, then it occurs in a[lo..hi]."

Step 2: initialisation. Before the loop, lo = 0 and hi = len(a) - 1, so a[lo..hi] is the whole array. "If target is in a then it is in `a`" is trivially true.

Step 3: maintenance. Assume $I$ and lo ⇐ hi. Then mid = (lo + hi) // 2 satisfies lo ⇐ mid ⇐ hi, so a[mid] is a valid element of the window. Three branches:

a[mid] == target: we return, so there is no next iteration to worry about (it is handled in step 5).
a[mid] < target: since a is sorted, every element a[j] with j ⇐ mid satisfies a[j] ⇐ a[mid] < target, so none of them equals target. If target is in a[lo..hi], it must therefore be in a[mid+1..hi]. Setting lo = mid + 1 keeps $I$ true.
a[mid] > target: symmetric. Every a[j] with j >= mid is at least a[mid] > target, so target (if present in the window) is in a[lo..mid-1]. Setting hi = mid - 1 keeps $I$ true.

Step 4: termination. Use the variant $V = \texttt{hi} - \texttt{lo} + 1$, the number of elements in the window. While the loop runs (lo ⇐ hi), $V \ge 1 > 0$. In the second branch the new window is a[mid+1..hi], which excludes at least a[mid]; in the third it is a[lo..mid-1], also excluding a[mid]. So $V$ decreases by at least 1 on every iteration that does not return. A positive integer cannot decrease for ever, so the loop terminates.

Step 5: exit. There are two ways out.

Early return in the first branch: a[mid] == target, so the postcondition holds with r = mid.
The loop condition fails: lo > hi, so a[lo..hi] is empty. By $I$, if target were in a it would be in this empty window, which is impossible. So target is not in a, and returning -1 is correct.

Both exits satisfy the postcondition, so binary search is totally correct. $\blacksquare$

Trace for target = 23 on the array above (indices 0–9):

`lo`	`hi`	`mid`	`a[mid]`	action
0	9	4	16	$16 < 23$: `lo = 5`
5	9	7	56	$56 > 23$: `hi = 6`
5	6	5	23	found: return 5

And for target = 7: (0, 9, mid 4, 16 > 7, hi = 3), (0, 3, mid 1, 5 < 7, lo = 2), (2, 3, mid 2, 8 > 7, hi = 1), and now $\texttt{lo} = 2 > 1 = \texttt{hi}$, so return -1. The window size went $10 \to 4 \to 2 \to 0$: the variant at work.

22.13.5. A second example: insertion sort

For insertion sort the natural invariant is "the prefix a[0:i] is sorted". You can even turn the invariant into a runtime check:

def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        # Invariant: a[0:i] is sorted (and is a permutation of the original a[0:i]).
        assert all(a[j] <= a[j + 1] for j in range(i - 1))
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]   # shift larger element right
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([5, 2, 9, 1, 5, 6]))

[1, 2, 5, 5, 6, 9]

Initialisation: when $i = 1$, a[0:1] has one element, and a one-element list is sorted.
Maintenance: the inner loop shifts every element of the sorted prefix that is larger than key one place right and drops key into the gap, so a[0:i+1] is sorted. (A full proof gives the inner loop its own invariant: "`a[j+2..i]` are all greater than key, and the prefix with the gap removed is sorted".)
Termination: a for loop over a finite range always terminates; the inner while has variant $j + 1$, which decreases by 1 each time and stays non-negative while the loop runs.
Exit: the outer loop ends with $i = n$ (the length), so the invariant says a[0:n], the whole list, is sorted.

assert statements like the one above turn your proof sketch into a check that runs during testing. They do not prove anything, but a failing invariant assertion pinpoints where the reasoning breaks, which is far more useful than a wrong final answer.

Termination is a separate obligation

An invariant proves the answer is right if the loop stops. It says nothing about whether it stops. Write lo = mid instead of lo = mid + 1 in binary search and the invariant is still maintained, but with lo = 0, hi = 1 and a[0] < target, mid is 0 and lo stays 0 for ever: the variant does not decrease. Always check both.

The proof assumed mathematical integers

In 2006 Joshua Bloch reported that the binary search in Java’s standard library, which had shipped for about nine years, had a bug. The line mid = (low + high) / 2 overflows when low + high exceeds $2^{31} - 1$, which happens for arrays of more than about a billion elements, giving a negative mid and an exception. The code followed the version in Jon Bentley’s Programming Pearls, which Bentley had proved correct, but the proof silently assumed that int behaves like the mathematical integers $\mathbb{Z}$. The fix is mid = low + (high - low) / 2. Python’s integers are unbounded, so the version above is safe; in C, C++, Java or Go it is not. A proof is only as good as its model of the machine.

22.13.6. Termination arguments

Every termination proof is the same argument: find a quantity in a well-ordered set (usually the non-negative integers) that strictly decreases. Because there is no infinite decreasing sequence of non-negative integers, the process must stop. That is the well-ordering principle again, the same fact that justified induction.

Euclid’s algorithm for the greatest common divisor (studied in Chapter 23) is a good example:

def gcd(a, b):
    while b != 0:
        # Variant: b is a non-negative integer that strictly decreases.
        a, b = b, a % b
    return a

print(gcd(252, 105))

For non-negative inputs, the new $b$ is $a \bmod b$, the remainder of dividing $a$ by $b$, which always satisfies $0 \le a \bmod b < b$. So $b$ strictly decreases and stays non-negative: the loop must reach $b = 0$.

Sometimes no variant is known:

def collatz_steps(n):
    steps = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return steps

print([collatz_steps(n) for n in range(1, 11)])
print(collatz_steps(27))

[0, 1, 7, 2, 5, 8, 16, 3, 19, 6]
111

A four-line loop nobody can prove terminates

The Collatz conjecture says the loop above terminates for every positive integer $n$. It has been checked by computer for every $n$ up to beyond $2^{68}$, yet nobody has a proof, and the value of $n$ does not decrease steadily (starting from 27, it takes 111 steps and climbs as high as 9232 before falling to 1). Paul Erdős reportedly said "mathematics may not be ready for such problems". It is a sobering reminder that "does this loop terminate?" can be beyond the reach of current mathematics, and, by Turing’s halting theorem, no algorithm can answer it for all programs.

22.13.7. Where you’d use this

Invariants are not a programming invention. Double-entry bookkeeping maintains the invariant "total debits = total credits" through every transaction; when the trial balance disagrees, an entry broke the invariant, and you know to look for it. Physics simulations check conservation laws the same way: in a game-physics or orbital simulation, total energy and momentum should stay constant (up to rounding), so a drifting total is the first sign of a bad time step. And a bank transfer between two accounts must preserve the sum of the balances at every observable moment, which is the invariant that database transactions exist to protect.

Invariant tracer

Step through binary search on an array you choose. At each iteration the lab shades the excluded regions grey (as in the figure), displays the invariant and the variant $\texttt{hi} - \texttt{lo} + 1$, and turns red if you edit the code (for example to lo = mid) in a way that breaks maintenance or termination. Try to find an edit that keeps the invariant but loops forever.

Try it: Trace binary search in Python

Formal verification and proof assistants

Everything in this section can be done by machine. Proof assistants such as Lean, Coq (now renamed Rocq), Isabelle and Agda check every step of a proof against the rules of logic; nothing is accepted on trust. In Lean, a theorem is a type and its proof is a program of that type; the system accepts it only if it type-checks. A tiny example in Lean 4:

theorem add_zero_right (n : Nat) : n + 0 = n := rfl

theorem zero_add_left (n : Nat) : 0 + n = n := by
  induction n with
  | zero => rfl
  | succ k ih => exact congrArg Nat.succ ih

The second proof is literally an induction: a zero (base) case and a succ k ($k + 1$) case that uses the hypothesis ih for $k$.

Large systems have been verified this way: the CompCert C compiler (Coq) is proved to preserve the meaning of the programs it compiles, and the seL4 operating-system microkernel (Isabelle) is proved to implement its specification. Tools such as Dafny, Why3 and Frama-C let you write loop invariants and variants as annotations in ordinary code and discharge the proof obligations automatically with SMT solvers. And mathematicians now formalise research mathematics in Lean’s mathlib library. The habits of this section (pre/postconditions, invariants, variants) are exactly the inputs these tools need.

US curriculum

Loop invariants and program correctness are not part of the US high-school mathematics curriculum. They appear in AP Computer Science A only informally, and properly in college Data Structures and Algorithms and Discrete Mathematics courses (the standard algorithms textbook by Cormen, Leiserson, Rivest and Stein uses the initialisation/maintenance/termination format above).

22.14. Exercises: programs

Recognition. What is a suitable invariant for this loop, which finds the largest element of a non-empty list a?
```
best = a[0]
for i in range(1, len(a)):
    if a[i] > best:
        best = a[i]
```
Application. After the following loop has completed $i$ iterations, what is the value of s? State and prove an invariant.
```
s = 0
for i in range(n):
    s += 2 * i + 1
```
Application. Prove that while x > 0: x = x // 2 terminates for every integer x.
Problem solving. A colleague writes binary search with while lo < hi: (instead of ⇐) but otherwise identical code. Find an input where it gives the wrong answer, and say which proof step fails.

Answers

Invariant: "at the top of the iteration with index $i$, best is the maximum of a[0:i]`". Initialisation: $i = 1$, `best = a[0] is the maximum of the one-element prefix. Maintenance: the new best is the larger of the old maximum and a[i], which is the maximum of a[0:i+1]. Exit: $i = n$, so best is the maximum of the whole list.
Invariant: after $i$ iterations, $s = i^2$. Initially $s = 0 = 0^2$. If $s = i^2$ before the iteration with loop variable $i$, it becomes $i^2 + 2i + 1 = (i+1)^2$, and $i + 1$ iterations have now completed. At the end, $s = n^2$. (This is the sum-of-odd-numbers theorem as a program.)
If $x \le 0$ the loop does not run. Otherwise the variant $x$ is a positive integer, and $x // 2 < x$ for $x \ge 1$ (it is at most $x/2$), and $x // 2 \ge 0$. A strictly decreasing sequence of non-negative integers is finite, so the loop ends.
Take a = [5], target = 5. Then lo = hi = 0, the test 0 < 0 is false, the loop never runs, and the function returns -1 although 5 is present. The exit step fails: lo < hi being false means lo >= hi, and when lo == hi the window a[lo..hi] has one element, not zero, so the invariant does not imply that target is absent.

22.15. Common proof errors

Most wrong proofs fail in a handful of recognisable ways. Learning the patterns is the fastest way to check your own work and to read other people’s.

22.15.1. Dividing by zero in disguise

Let $a = b$, with $b \neq 0$. Then:

\[\begin{aligned} a^2 &= ab \qquad\text{(multiply both sides by } a\text{)} \\ a^2 - b^2 &= ab - b^2 \qquad\text{(subtract } b^2\text{)} \\ (a + b)(a - b) &= b(a - b) \qquad\text{(factor both sides)} \\ a + b &= b \qquad\text{(divide by } a - b\text{: INVALID, since } a - b = 0\text{)} \\ 2b &= b \qquad\text{(substitute } a = b\text{)} \\ 2 &= 1. \qquad\text{(divide by } b\text{)} \end{aligned}\]

Every line is correct except the fourth. Since $a = b$, $a - b = 0$, and cancelling a zero factor is not allowed. Whenever you cancel or divide, ask: could this be zero?

22.15.2. The broken bridge: all horses are the same colour

"Claim: in any set of $n \ge 1$ horses, all horses are the same colour. Base case: one horse is the same colour as itself. Step: given $k + 1$ horses, remove the first: the remaining $k$ are the same colour by the IH. Remove the last instead: those $k$ are also the same colour. The two groups overlap, so all $k + 1$ share a colour."

The base case is right, and the step is right for $k \ge 2$. It fails at $k = 1 \to 2$: with two horses, removing the first leaves {horse 2}, removing the last leaves {horse 1}, and these groups do not overlap. One broken link and the whole chain collapses. Lesson: check that the inductive step works for the smallest $k$, not just "typical" large $k$.

22.15.3. A catalogue of errors

The usual suspects

Proof by example: checking cases for a "for all" claim (the Euler polynomial).
Circular reasoning: assuming the conclusion, or something equivalent to it, along the way.
Proving the converse: showing $Q \Rightarrow P$ when asked for $P \Rightarrow Q$.
Reusing a variable: "let $a = 2k+1$ and $b = 2k+1$" silently makes $a = b$.
Hidden division by zero or square roots of negatives; taking square roots of both sides without $\pm$.
Non-exhaustive cases: forgetting zero, negatives, the empty set, or $n = 1$.
Missing or wrong base case; too few base cases for strong induction.
Inductive step that fails for small $k$ (the horses).
Swapped quantifiers: "for every $\varepsilon$ there is a $\delta$" is not "there is a $\delta$ that works for every $\varepsilon$" (see Chapter 21).
"Clearly", "obviously", "similarly" covering a gap. If a step is clear, it costs one line to write it down.
Proof about the model, not the machine: the binary-search overflow.

Spot the bug

A gallery of short "proofs", each with exactly one flaw (division by zero, missing base case, non-exhaustive cases, proving the converse, a broken small case). Click the line you think is wrong; the lab explains the error and shows a counterexample or a corrected proof. A good self-test before the mastery check.

22.16. Choosing a proof technique

You now have six tools. Which should you pick? The flowchart summarises the heuristics developed in this chapter. It is a starting point, not an algorithm: real proofs often combine techniques (the $\sqrt 2$ proof used a direct proof inside a contrapositive inside a contradiction).

Figure 204. A first guess at which technique to try. Whatever the shape, spend a few minutes hunting for a counterexample before investing in a proof.

In words:

Is it false? Try edge cases and a quick script first.
Indexed by integers or defined recursively? Induction; strong induction if the step needs more than the previous case; structural induction for trees, lists and expressions.
"If $P$ then $Q$" with a concrete $P$? Direct proof.
Conclusion is negative, or an "or", or $P$ is awkward to unpack? Contrapositive.
Claim is a bare negative or about non-existence or infinitude? Contradiction.
Objects split naturally into types? Cases, with an exhaustiveness check.
Is it code? Invariant + variant, which is induction plus well-ordering.

22.17. Interactive tools

Browser tools on the companion website that go with this chapter. Each example link in the chapter opens one of them with that example already set up.

Language sandbox

22.18. Mastery check

Prove that the sum of any three consecutive integers is divisible by 3.
Prove: for every integer $n$, if $5n + 4$ is odd then $n$ is odd. Name the technique.
Prove that $\log_2 3$ is irrational.
Disprove: "for every real number $x$, $x^2 > x$."
Prove by induction that $\displaystyle\sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}$ for all $n \ge 1$.
Prove by induction that $3^n \ge 2n + 1$ for all $n \ge 0$.

State a loop invariant and a variant for the following function (assume e >= 0), and use them to prove it returns $b^e$.

def power(b, e):
    result, i = 1, 0
    while i < e:
        result *= b
        i += 1
    return result

Find the error: "Claim: every positive integer is less than 100. Inductive step: assume $k < 100$. Then $k + 1 < 101$… and so on, so $k + 1 < 100$."

Decision rule: All correct without hesitation → move on to Chapter 23, where you will use these techniques constantly. Stuck on 1–4 → reread Section 22.3, Section 22.4 and Section 22.5. Stuck on 5–6 → reread Section 22.9 and redo its exercises. Stuck on 7 → reread Section 22.13. Stuck on 8 → reread Section 22.15.

Mastery check answers

Direct. Three consecutive integers are $n - 1, n, n + 1$. Their sum is $(n-1) + n + (n+1) = 3n$, which is divisible by 3.
Contrapositive: if $n$ is even then $5n + 4$ is even. Let $n = 2k$; then $5n + 4 = 10k + 4 = 2(5k + 2)$, which is even. Hence if $5n + 4$ is odd, $n$ is odd.
Contradiction. Suppose $\log_2 3 = p/q$ with integers $p, q$, $q > 0$. Since $\log_2 3 > 0$ (because $3 > 1$), also $p > 0$. Then $2^{p/q} = 3$, and raising both sides to the power $q$ gives $2^p = 3^q$. The left side is even ($p \ge 1$) and the right side is odd (a product of odd numbers). Contradiction.
Counterexample: $x = 1$ gives $1 > 1$, false. (Any $x$ with $0 \le x \le 1$ works, e.g. $x = \tfrac12$.)
Base $n = 1$: left $1 \cdot 2 = 2$, right $\frac{1 \cdot 2 \cdot 3}{3} = 2$. Step:

\[\begin{aligned} \sum_{i=1}^{k+1} i(i+1) &= \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) \qquad\text{(IH)} \\ &= \frac{k(k+1)(k+2) + 3(k+1)(k+2)}{3} \\ &= \frac{(k+1)(k+2)(k+3)}{3}. \qquad\text{(factor out } (k+1)(k+2)\text{)} \end{aligned}\]
Base $n = 0$: $3^0 = 1 \ge 1 = 2 \cdot 0 + 1$. Step: assume $3^k \ge 2k + 1$. Then $3^{k+1} = 3 \cdot 3^k \ge 3(2k + 1) = 6k + 3 \ge 2k + 3 = 2(k+1) + 1$, using $6k \ge 2k$ for $k \ge 0$.
Invariant: $\texttt{result} = b^{\,i}$ and $0 \le i \le e$. Initialisation: $1 = b^0$, $i = 0$. Maintenance: if $\texttt{result} = b^i$ and $i < e$, then after the body $\texttt{result} = b^{i+1}$ and $i + 1 \le e$. Variant: $e - i$, a non-negative integer that decreases by 1 each iteration, so the loop terminates. Exit: $i \ge e$ and $i \le e$ give $i = e$, so $\texttt{result} = b^e$.
The base case is missing ($1 < 100$ is true, so that part is easy to add), but the real error is in the inductive step, which does not follow: $k < 100$ gives only $k + 1 < 101$, which allows $k + 1 = 100$; "and so on" hides the gap. Indeed $k = 99$ satisfies the hypothesis while $k + 1 = 100$ fails the conclusion, so $P(k) \Rightarrow P(k+1)$ is false. (The claim is false: 100 is a counterexample.)

`lo`	`hi`	`mid`	`a[mid]`	action
0	9	4	16	\(16 < 23\): `lo = 5`
5	9	7	56	\(56 > 23\): `hi = 6`
5	6	5	23	found: return 5

\(d\)	0	1	2	3	4	5	6	7	8	9
\(d^2\)	0	1	4	9	16	25	36	49	64	81
last digit	0	1	4	9	6	5	6	9	4	1