Edexcel A-Level Mathematics

What a proof is

A proof starts from assumptions that are given or already established and moves through a series of logical steps to a conclusion, each step following from the ones before. A calculation that works for a few numbers is evidence, not a proof, because the claim is usually about every number in some set. A proof either covers the whole set at once, as algebra does, or covers every case one by one.

Some notation makes the logic compact. The symbol $\Rightarrow$ means "implies", so $x = 3 \Rightarrow x^2 = 9$, but the reverse fails, since $x^2 = 9$ also allows $x = -3$. The symbol $\Leftrightarrow$ means "if and only if" and is used when each statement implies the other. An identity, written with $\equiv$, is true for every value of the variable, unlike an equation, which is true only for some. The letters $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ and $\mathbb{R}$ stand for the natural numbers, the integers, the rational numbers and the real numbers.

Proof by deduction

In proof by deduction you start from known facts and algebraic definitions and reason directly to the result. It is the method used throughout the subject, whenever a formula is derived. The usual first step is to write the objects in a general form: an even number is $2k$ and an odd number is $2k + 1$ for an integer $k$; consecutive integers are $n$ and $n + 1$; a multiple of 5 is $5k$.

To prove that the sum of the squares of two consecutive integers is always odd, let the integers be $n$ and $n + 1$:

Since $n^2 + n$ is an integer, this has the form $2k + 1$, so it is odd for every integer $n$.

To prove that $n^2 - 8n + 20$ is positive for every real $n$, complete the square:

A square is never negative, so the expression is at least 4, and in particular positive.

A written proof should state what is being assumed, keep each step so small that it can be checked, and end with a sentence saying what has been shown. Where a step divides, the divisor must be known to be non-zero. Where a step squares both sides of an inequality, both sides must be known to be non-negative.

Proof by exhaustion

In proof by exhaustion the possibilities are split into a finite number of cases, and the result is shown to hold in every one. The cases must cover everything and there must be few enough of them to check.

The first use is to split into cases by type. To prove that the square of an integer leaves remainder 0 or 1 on division by 4, take the two types of integer:

• if $n = 2k$, then $n^2 = 4k^2$, which leaves remainder 0;
• if $n = 2k + 1$, then $n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$, which leaves remainder 1.

Every integer is one of the two types, so the result holds for all.

The second use is to check each member of a small finite set. To prove that for every prime $p$ with $7 < p < 30$ the number $p^2 - 1$ is a multiple of 24, list the primes: 11, 13, 17, 19, 23 and 29. Then

All six are multiples of 24, so the statement is proved for this range. It says nothing about primes outside it.

Disproof by counter-example

To show that a statement about all members of a set is false, one member for which it fails is enough. This is a counter-example, and it needs no general argument.

The statement "$2^n + 1$ is prime for every positive integer $n$" holds for $n = 1$ (3), $n = 2$ (5) and $n = 4$ (17), but at $n = 3$ it gives $2^3 + 1 = 9 = 3 \times 3$, which is not prime. The statement "$n^2 + n + 41$ is prime for every positive integer $n$" is true for every $n$ from 1 to 39, and false at $n = 41$, where $41^2 + 41 + 41 = 1763 = 41 \times 43$. Many cases agreeing does not make a proof, and one exception disproves.

A counter-example must be checked completely: state the value chosen, evaluate the expression and say why the result contradicts the claim. Finding one counter-example disproves a universal claim, but finding examples that agree proves nothing.

Proof by contradiction

In proof by contradiction you assume that the statement is false, follow the consequences, and reach something impossible, such as a number that is both odd and even. Since every step after the assumption was valid, the assumption must have been wrong, so the statement is true.

The irrationality of the square root of 2

A number is rational if it can be written as a fraction of two integers, and it can always be written in lowest terms, with no common factor between numerator and denominator. Suppose $\sqrt{2}$ is rational, so $\sqrt{2} = \dfrac{p}{q}$ with $p$ and $q$ integers that have no common factor. Then

So $p^2$ is even. If $p$ were odd then $p^2$ would be odd, so $p$ is even, and $p = 2m$ for an integer $m$. Substituting,

so $q^2$ is even, and by the same argument $q$ is even. Now $p$ and $q$ are both even, which contradicts the assumption that they have no common factor. Therefore $\sqrt{2}$ is irrational.

There are infinitely many primes

Suppose instead that there are finitely many primes, and list them all: $p_1, p_2, \ldots, p_k$. Form the number

Dividing $N$ by any $p_i$ leaves remainder 1, so no prime on the list divides $N$. But $N > 1$, so it is either prime itself or has a prime factor, and in both cases there is a prime that is not on the list. This contradicts the assumption that the list held all the primes, so there are infinitely many.

Applying the method to an unfamiliar statement

The pattern is the same each time: state the negation of the claim exactly, use it to derive a fact about integers, and find two facts that cannot both hold. To prove that $\log_2 3$ is irrational, suppose that $\log_2 3 = \dfrac{p}{q}$ with $p$ and $q$ positive integers. Then $2^{p/q} = 3$, and raising to the power $q$ gives $2^p = 3^q$. The left side is even, since $p \geq 1$, and the right side is odd, since it is a power of 3. An integer cannot be both, so the assumption is false and $\log_2 3$ is irrational.

To prove that there are no integers $a$ and $b$ with $a^2 - b^2 = 2$ (a statement about integers, so the cases below are exhaustive), suppose there are. Since $a^2 - b^2 = (a - b)(a + b)$, the numbers $a - b$ and $a + b$ differ by $2b$, which is even, so they are both even or both odd. If both are odd, their product is odd and cannot equal 2. If both are even, their product is a multiple of 4 and cannot equal 2. Both cases contradict, so no such integers exist.

Choosing a method