What a proof is

The previous lesson derived a sum formula by writing a list forwards and backwards with dots in the middle, and the first lesson asserted that no fraction squares to $2$ without giving the argument. Both are believed by every mathematician, and neither has yet been established here.

This lesson is about the difference between believing and establishing. It assumes everything the course has covered, and it settles the two open claims using techniques that are the whole toolkit: direct argument, contrapositive, contradiction and induction.

Why evidence is not enough

A mathematical claim usually quantifies over infinitely many cases. "The sum of the first $n$ odd numbers is $n^{2}$ " is not one statement but infinitely many, one for each $n$ , and checking a hundred of them leaves infinitely many unchecked.

That would be pedantry if patterns held reliably. They do not. Euler's $n^{2} + n + 41$ from the previous lesson gives a prime for every $n$ from $0$ to $39$ and fails at $40$ . Fermat conjectured in 1640 that every number of the form $2^{2^{n}} + 1$ is prime, having checked $n$ up to $4$ , and Euler showed in 1732 that the next one factors: $2^{32} + 1 = 4 {,} 294 {,} 967 {,} 297 = 641 \times 6 {,} 700 {,} 417$ . Five successes and then failure.

A proof is an argument that the claim cannot fail, given the assumptions, for any case at all. It replaces sampling with necessity. This is the trade that makes mathematics different from the empirical sciences: the conclusions are narrower, since they hold only under stated assumptions, and within that scope they are permanent. A theorem of Euclid's is as true now as it was in 300 BCE, which cannot be said of any measurement of that era.

Statements, and the asymmetry of the counterexample

Two shapes of claim behave differently under testing. A claim about all cases, "every prime above $2$ is odd", cannot be established by examples but can be destroyed by a single one that fails. A claim about some case, "there exists a prime between $90$ and $100$ ", is established by one example, namely $97$ , and refuting it requires an exhaustive argument.

So the first thing to do with a suspicious claim about all cases is to hunt for a counterexample, and finding one ends the matter with no further work.

Example. Is it true that $2^{p} - 1$ is prime whenever $p$ is prime?

Test the small cases: $p = 2$ gives $3$ , $p = 3$ gives $7$ , $p = 5$ gives $31$ , $p = 7$ gives $127$ , all prime, and the pattern looks solid. At $p = 11$ it gives $2047$ , which is $23 \times 89$ . The claim is false, and one line of arithmetic settles it. These numbers are the Mersenne primes when they are prime, and which primes $p$ produce them is unsolved to this day.

Now you. Is it true that $n^{2} - n + 11$ is prime for every natural number $n$ ? Either find a counterexample or say why the search should start where it does.

Answer

It fails at $n = 11$ , where the expression is $121 - 11 + 11 = 121 = 11^{2}$ . The search should start there because every term is a multiple of $11$ when $n$ is, which is the same mechanism that breaks Euler's polynomial at $n = 41$ .

Direct proof

The plainest structure assumes the hypothesis and reasons forward to the conclusion, using definitions and established results. The essential move is to replace a word with its definition, since a definition is the only thing that lets an argument get started.

Claim: the sum of two even numbers is even. An even number is by definition $2 k$ for some integer $k$ . So take two of them, $2 k$ and $2 m$ . Their sum is $2 k + 2 m = 2 (k + m)$ by distributivity, and $k + m$ is an integer, so the sum has the required form and is even. The proof is three lines and it covers infinitely many pairs at once, which is exactly what checking cases could not do.

The same shape proves that the product of two odd numbers is odd. Odd means $2 k + 1$ , so the product is $(2 k + 1) (2 m + 1) = 4 k m + 2 k + 2 m + 1 = 2 (2 k m + k + m) + 1$ , which is odd. Notice that the algebra doing the work is the distributivity of the second lesson, and that the derivation of $(- 1) (- 1) = 1$ given there was itself a direct proof.

Contrapositive, and the converse that is not the same

Some claims resist a direct attack. Show that if $n^{2}$ is even then $n$ is even, and the hypothesis $n^{2} = 2 k$ gives nothing useful to factor.

Every implication "if $P$ then $Q$ " is logically identical to its contrapositive, "if not $Q$ then not $P$ ". If rain implies wet ground, then dry ground implies no rain, and the two say the same thing. So instead prove: if $n$ is odd then $n^{2}$ is odd. That is direct and immediate, since $n = 2 k + 1$ gives $n^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ , which is odd. The original claim follows with no further work.

The converse, "if $Q$ then $P$ ", is a different statement and is not implied. Wet ground does not imply rain. Confusing an implication with its converse is the most frequent error in reasoning inside mathematics and outside it, and the discipline is to state which of the two is being claimed. When both hold, the statement is written "if and only if", and it requires two proofs. The factor theorem in the polynomial lesson was such a claim, and it needed both directions.

Contradiction, and the diagonal of the square

Proof by contradiction assumes the claim is false and derives an impossibility, so the assumption cannot stand. It is the technique the first lesson promised, and here is the debt paid.

Claim: there is no rational number whose square is $2$ .

Suppose there were. Then $\sqrt{2} = p / q$ for integers $p$ and $q$ with no common factor, since any common factor can be cancelled first, and this reduction is where the contradiction will eventually be trapped. Squaring gives $2 = p^{2} / q^{2}$ , so

p^{2} = 2 q^{2}

The right side is even, so $p^{2}$ is even, so by the contrapositive result proved above $p$ is even. Write $p = 2 m$ . Substituting gives $4 m^{2} = 2 q^{2}$ , so $q^{2} = 2 m^{2}$ , and the same argument makes $q$ even too.

But $p$ and $q$ were assumed to have no common factor, and both are now even, so both are divisible by $2$ . That is a contradiction, so the assumption that $\sqrt{2}$ is rational is false. The diagonal of a unit square has a length no fraction names, which is what the Pythagoreans found and what forced the real line into existence in the first lesson.

Euclid's proof that the primes never run out has the same shape and is worth knowing. Suppose there were finitely many, $p_{1}$ through $p_{k}$ . Form $N = p_{1} p_{2} \dots p_{k} + 1$ . Dividing $N$ by any prime on the list leaves remainder $1$ , so no listed prime divides it. Yet every integer above $1$ has a prime factor, so $N$ has one, and it is not on the list, contradicting the assumption that the list was complete. Note what the argument does not claim: $N$ need not itself be prime. With the first six primes, $N = 30031 = 59 \times 509$ , and both factors are missing from the list, which is all the proof requires.

Induction, and the two open sum formulas

Contradiction and direct argument still do not reach a claim indexed by every natural number. For that there is mathematical induction, and the picture is a line of dominoes: knock over the first, and guarantee that each one knocks over its neighbour, and all of them fall, however many there are.

Formally, to prove a statement $S (n)$ for every natural $n$ , prove two things. The base case: $S (1)$ is true. The inductive step: if $S (n)$ is true then $S (n + 1)$ is true. Both are finite tasks, and together they establish infinitely many statements. The step is not the assumption that $S (n)$ is true for all $n$ , which would be circular; it is the proof of a conditional, and that distinction is the whole of the technique.

Example. Prove that the sum of the first $n$ odd numbers is $n^{2}$ .

Base case: for $n = 1$ the sum is $1$ and $1^{2} = 1$ , so it holds. Inductive step: assume $1 + 3 + dots + (2 n - 1) = n^{2}$ for some particular $n$ . The next odd number is $2 n + 1$ , so the sum to $n + 1$ terms is $n^{2} + (2 n + 1)$ by the assumption, and $n^{2} + 2 n + 1 = (n + 1)^{2}$ , which is the claim for $n + 1$ . Both parts hold, so the formula is true for every $n$ . The algebra in the step is the perfect square from the third lesson, doing the essential work.

Now you. Prove by induction that $1 + 2 + dots + n = n (n + 1) / 2$ , the formula the previous lesson obtained by pairing.

Answer

Base case: at $n = 1$ the sum is $1$ and $1 \times 2 / 2 = 1$ . Step: assume the sum to $n$ is $n (n + 1) / 2$ . Then the sum to $n + 1$ is $n (n + 1) / 2 + (n + 1) = (n + 1) big (n / 2 + 1 big) = (n + 1) (n + 2) / 2$ , which is the formula with $n + 1$ in place of $n$ . So it holds for every $n$ .

Induction also handles the geometric sum of the previous lesson, whose derivation by shifting and subtracting relied on dots standing in for unwritten terms. Assume $S_{n} = a (1 - r^{n}) / (1 - r)$ . Adding the next term $a r^{n}$ gives $a (1 - r^{n}) / (1 - r) + a r^{n}$ , and putting it over the common denominator gives $a (1 - r^{n} + r^{n} - r^{n + 1}) / (1 - r) = a (1 - r^{n + 1}) / (1 - r)$ , which is the formula one step on. With the base case $S_{1} = a$ checked directly, the formula is proved for every $n$ , and every loan calculation in the previous lesson now stands on something firmer than a persuasive picture.

Example. Prove that $2^{n} > n^{2}$ for every $n \geq 5$ .

Base case: at $n = 5$ , $32 > 25$ . Note that the claim is false at $n = 4$ , where both are $16$ , which is why the base is placed at $5$ . Step: assume $2^{n} > n^{2}$ for some $n \geq 5$ . Then $2^{n + 1} = 2 \times 2^{n} > 2 n^{2}$ , so it is enough to show $2 n^{2} \geq (n + 1)^{2}$ , that is $n^{2} - 2 n - 1 \geq 0$ . By the quadratic formula that holds for $n \geq 1 + \sqrt{2} = 2.414$ , and $n \geq 5$ comfortably satisfies it. So the claim propagates.

Now you. Prove that $n^{3} - n$ is divisible by $3$ for every natural $n$ .

Answer

Base case: at $n = 1$ the value is $0$ , which is divisible by $3$ . Step: assume $n^{3} - n = 3 k$ . Then $(n + 1)^{3} - (n + 1) = n^{3} + 3 n^{2} + 3 n + 1 - n - 1 = (n^{3} - n) + 3 (n^{2} + n) = 3 k + 3 (n^{2} + n) = 3 (k + n^{2} + n)$ , a multiple of $3$ .

What proof does not give you

Three honest limits. A proof establishes a conclusion from assumptions, and it says nothing about whether the assumptions describe anything real. Euclidean geometry is proved from Euclid's postulates, and physical space does not obey them.

A proof can be wrong, and long ones sometimes are. Errors surface in refereeing, and famous arguments have collapsed and been repaired: Wiles' first version of the proof of Fermat's last theorem, announced in 1993, had a gap that took a further year and a collaborator to close.

And no system of axioms strong enough to describe arithmetic can prove every true statement about the natural numbers. Gödel established that in 1931, and it is not a loophole any working mathematician trips over, but it does mean that "provable" and "true" are not the same word.

Where this ends and the next thing starts

The subject is now closed. Numbers were built from counting to the continuum, algebra was reduced to a short list of laws, equations were solved, functions were defined, drawn and inverted, and polynomials, exponentials, logarithms and the circular functions were each derived and put to work on data. The two arguments the course deferred have been given, and the technique that gives them is the one that would prove the rest.

What remains untouched is the question every one of these functions raises and none of them answers: how fast is it changing right now, and what does the area under it total. Both are limits, and both require the completeness of the real line established in the first lesson. That is calculus, and everything needed to start it is now in place.