Why prove anything

A pattern that holds in every case anyone has checked feels like a fact, and in mathematics it can still be false.

This lesson starts with three such patterns, each of which survived far longer than anyone would need to be convinced, and each of which failed. They are the reason mathematics settles its claims by proof rather than by evidence. The second half of the lesson says what a proof is, why it starts from definitions, and writes the first few out in full. It assumes school algebra and nothing else.

Forty primes, then a square

In 1772 Euler noticed that the expression $n^{2} + n + 41$ produces primes with remarkable persistence. At $n = 0$ it gives $41$ , then $43$ , $47$ , $53$ , $61$ , $71$ , and every value up to $n = 39$ , where it gives $1601$ , is prime. Forty consecutive successes is more than most people would ask before believing a rule.

At $n = 40$ the value is $1681$ , and $1681 = 41^{2}$ . Once it has happened it is easy to see why. Write the expression at $n = 40$ with the first two terms grouped: $40^{2} + 40 = 40 (40 + 1) = 40 \times 41$ , so the whole thing is $40 \times 41 + 41 = 41 \times 41$ .

The same thought shows that $n = 41$ fails too: every term of $41^{2} + 41 + 41$ is a multiple of $41$ , and the value is $1763 = 41 \times 43$ . The structure that breaks the pattern was visible in the formula from the start. The forty checks established forty facts and said nothing about the forty-first, because nothing in them said why the values were prime. A check tells you what happened, not what must happen.

Doubling that stops at thirty-one

Place points on a circle and join every pair with a straight chord, taking care that no three chords pass through the same interior point. Count the regions the chords cut the disc into. One point makes no chord, so there is $1$ region. Two points give one chord and $2$ regions. Three points give a triangle and $4$ regions, four points give $8$ , and five give $16$ .

The sequence $1, 2, 4, 8, 16$ is as clean a pattern as mathematics offers, and the obvious guess is that six points give $32$ . They give $31$ , and no arrangement of six points does better. (If the six points are the corners of a regular hexagon, the three long diagonals meet at the centre, which breaks the rule about three chords, and the count drops to $30$ .)

Here too the failure makes sense once the right quantity is counted. Add the chords one at a time. A new chord that crosses $k$ chords already drawn passes through $k + 1$ existing regions and splits each of them in two, so it adds $k + 1$ regions. Summing over all the chords, the total is $1$ for the starting disc, plus $1$ for each chord, plus $1$ for each crossing point. With $n$ points there are $(\binom{n}{2})$ chords (one per pair of points, so $n (n - 1) / 2$ ), and every choice of four points produces exactly one crossing (where the diagonals of their quadrilateral meet), so there are $(\binom{n}{4})$ crossings. For six points that is $1 + 15 + 15 = 31$ , and for seven it is $1 + 21 + 35 = 57$ , nowhere near $64$ .

The powers of two were a coincidence of small numbers: $2^{n - 1}$ and $1 + (\binom{n}{2}) + (\binom{n}{4})$ agree up to five points and then part company. The argument rests on the sentence "every choice of four points produces exactly one crossing", and a careful reader should want that sentence justified. Justifying sentences like it is what this course is about.

Nine hundred million confirmations

Perhaps people should simply check more. The third pattern answers that. Count the prime factors of a whole number with repeats, so that $12 = 2 \times 2 \times 3$ has three and $9 = 3 \times 3$ has two, and give $1$ zero. Among the numbers from $1$ to $10$ , five ( $2$ , $3$ , $5$ , $7$ and $8$ ) have an odd number of prime factors, and up to $100$ it is fifty-one.

In 1919 George Pólya conjectured that this always happens: for every $n$ greater than $1$ , at least half of the numbers from $1$ to $n$ have an odd number of prime factors. It was checked by hand and later by machine over enormous ranges, and it held for every $n$ anyone tested.

In 1958 Brian Haselgrove proved that it fails somewhere, by an argument that showed a counterexample exists without producing one. In 1980 Minoru Tanaka found the first one by computer. It is 906,150,257. Up to that number, 453,075,128 have an odd number of prime factors and 453,075,129 have an even number, so the odd ones are outnumbered by one. Every $n$ from $2$ to 906,150,256 obeys the conjecture.

A claim about every natural number is a claim about infinitely many cases, and any finite collection of checks, however large, leaves infinitely many unchecked. Nine hundred million confirmations are exactly as far from infinity as forty. Evidence, which is how the empirical sciences rightly work, cannot establish a mathematical claim of this kind. It can refute one: a single failure, such as $1681$ or Tanaka's number, disposes of a claim about every case completely.

What a proof is

A proof is a finite chain of statements, each of which is justified by one of three things: a definition, an axiom (a statement taken as a starting point and not argued for), or a result that has already been proved. The last statement in the chain is the claim. Because every link is justified, the claim cannot fail in any case the chain covers, and one chain can cover infinitely many cases.

A proof is not an argument that makes the claim plausible, and it is not a picture: the chords on a circle suggested $32$ and delivered $31$ . What a proof offers is checkability. A reader can take each line, ask what justifies it, and find the answer in a definition, an axiom or an earlier theorem. If every line survives that question, the reader has no choice but to accept the conclusion, without needing to trust the writer.

This is the trade mathematics makes. Its conclusions hold only under the stated assumptions, and within them they are permanent. Euclid's proof that there are infinitely many primes, written around 300 BCE, is as correct now as it was then, which no measurement from that century can claim.

Proofs in this course are written in sentences. Symbols appear where they are clearer, but words such as "suppose", "since" and "so" carry the argument, because they say which statement follows from which. A column of bare equations often hides exactly the step that needed justifying.

Definitions do the work

A proof starts from definitions. This is the habit that most separates proof from school mathematics: a word such as "even" stops being something you recognise and becomes an exact statement you can use.

An integer $n$ is even if there is an integer $k$ with $n = 2 k$ . An integer $n$ is odd if there is an integer $k$ with $n = 2 k + 1$ . Everything this lesson proves about parity comes from those two sentences and the ordinary rules of algebra for integers, such as the fact that sums and products of integers are integers and that multiplication distributes over addition.

The definition settles questions that recognition leaves vague. Is $0$ even? Yes, since $0 = 2 \times 0$ . Is $- 3$ odd? Yes, since $- 3 = 2 \times (- 2) + 1$ . The school test "the last digit is $0$ , $2$ , $4$ , $6$ or $8$ " agrees, but it is a fact about base-ten notation and would need its own proof before it could be used.

Notice also what the definitions do not say. Nothing in them states that every integer is even or odd, or that no integer is both. Both are true, but both need proofs of their own, which rest on division with remainder, and a proof that quietly relies on them before they are proved is incomplete.

The word "some" in the definitions matters too. To show a number is even you must produce the $k$ , or show that one exists. To use the fact that a number is even you may name its $k$ and work with it. That is the whole mechanism of the proofs below.

A first proof

The sum $3 + 5 = 8$ is even, and so is $7 + 11 = 18$ , but those are evidence. The goal is an argument that covers every pair at once.

Example. Prove that the sum of two odd integers is even.

Let $a$ and $b$ be odd integers. By the definition of odd, there is an integer $k$ with $a = 2 k + 1$ , and there is an integer $m$ with $b = 2 m + 1$ . Then $a + b = (2 k + 1) + (2 m + 1) = 2 k + 2 m + 2 = 2 (k + m + 1)$ . Since $k$ and $m$ are integers, $k + m + 1$ is an integer. So $a + b$ is twice an integer, and by the definition of even, $a + b$ is even.

Three details are worth copying. It names arbitrary odd integers, so nothing is assumed about them except that they are odd. It uses two different letters, $k$ and $m$ , because $a$ and $b$ need not be equal; one letter would have proved the claim only for a number added to itself. And its last sentence names the definition it has satisfied, so the reader sees the chain close.

Now you. Prove that the sum of an even integer and an odd integer is odd.

Answer

Let $a$ be an even integer and $b$ an odd integer. By the definitions, there is an integer $k$ with $a = 2 k$ and an integer $m$ with $b = 2 m + 1$ . Then $a + b = 2 k + 2 m + 1 = 2 (k + m) + 1$ . Since $k + m$ is an integer, $a + b$ has the form twice an integer plus one, so by the definition of odd, $a + b$ is odd.

Example. Prove that the product of two odd integers is odd.

Let $a$ and $b$ be odd integers, so that $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then $a b = (2 k + 1) (2 m + 1) = 4 k m + 2 k + 2 m + 1 = 2 (2 k m + k + m) + 1$ . Since $k$ and $m$ are integers, so is $2 k m + k + m$ . Therefore $a b$ is twice an integer plus one, and by the definition of odd, $a b$ is odd.

Now you. Prove that if $a$ is an even integer and $b$ is any integer, then $a b$ is even.

Answer

Let $a$ be an even integer and $b$ any integer. By the definition of even, there is an integer $k$ with $a = 2 k$ . Then $a b = 2 k b = 2 (k b)$ . Since $k$ and $b$ are integers, $k b$ is an integer, so $a b$ is twice an integer and, by the definition of even, $a b$ is even.

Proving that a pattern fails

Proof can also show that a pattern fails, and why, far beyond a single counterexample. For this the definitions needed are those of prime and composite: an integer greater than $1$ is prime if its only positive divisors are $1$ and itself, and composite if it is the product of two integers each greater than $1$ .

Example. Prove that $n^{2} + n + 41$ is composite whenever $n$ is a positive multiple of $41$ .

Let $n$ be a positive multiple of $41$ , so that $n = 41 m$ for some integer $m \geq 1$ . Then $n^{2} + n + 41 = 41^{2} m^{2} + 41 m + 41 = 41 (41 m^{2} + m + 1)$ . The first factor, $41$ , is greater than $1$ . Since $m \geq 1$ , the second factor is at least $41 + 1 + 1 = 43$ , so it is greater than $1$ as well. Therefore $n^{2} + n + 41$ is a product of two integers each greater than $1$ , and by definition it is composite.

No amount of checking could do this: the proof shows Euler's expression fails at $n = 41$ , $82$ , $123$ and infinitely many other values, and why.

Now you. Prove that $n^{2} + n + 41$ is composite whenever $n = 41 m + 40$ for some integer $m \geq 0$ . (At $m = 0$ this is the failure at $n = 40$ .)

Answer

Let $n = 41 m + 40$ with $m \geq 0$ an integer. Expanding, $n^{2} = 1681 m^{2} + 3280 m + 1600$ , so $n^{2} + n + 41 = 1681 m^{2} + 3321 m + 1681 = 41 (41 m^{2} + 81 m + 41)$ . The factor $41$ is greater than $1$ , and since $m \geq 0$ the second factor is at least $41$ , so it is greater than $1$ too. So $n^{2} + n + 41$ is a product of two integers each greater than $1$ , and is composite.

What the proofs needed

Every proof in this lesson began by working out what its claim actually asserted. "The sum of two odd integers is even" turned out to mean: for any integers $a$ and $b$ , if $a$ is odd and $b$ is odd, then $a + b$ is even. Hidden in that ordinary sentence are an "if ... then" and a "for any", and the proof's shape came from them: take arbitrary $a$ and $b$ , assume they are odd, and reach the conclusion. Refuting Pólya's conjecture needed the same precision in reverse: knowing that one $n$ with fewer than half is enough means knowing exactly what the negation of "for every $n$ " says.

So statements have to be read exactly: "and", "or", "not" and "if ... then" do not always mean in mathematics what they mean in conversation. The next lesson fixes those meanings, and the conditional, the "if ... then" that every theorem is written in, turns out to mean something that surprises almost everyone the first time.