OCR A-Level Mathematics A

What a proof is

A proof starts from assumptions and facts already established and moves through logical steps to a conclusion, with nothing left to trust. A single worked example never proves a general statement, because the next case might behave differently. A proof has to cover every case the statement claims.

The vocabulary matters. An integer is a whole number (positive, negative or zero), a rational number can be written as $\dfrac{p}{q}$ with $p$ and $q$ integers and $q \ne 0$, and a real number is any point on the number line. A real number that is not rational is irrational. The symbol $\mathbb{Z}$ stands for the integers, $\mathbb{Q}$ for the rationals and $\mathbb{R}$ for the reals.

Logical connectives

Three symbols connect statements. $P \Rightarrow Q$ means "if $P$ then $Q$": whenever $P$ is true, $Q$ is true as well. $P \Leftarrow Q$ is the same statement the other way round. $P \Leftrightarrow Q$ means both hold, and is read "if and only if" (often shortened to "iff"). It says the two statements are equivalent.

The two directions are separate claims and one does not give the other. If $x = 3$ then $x^2 = 9$, so $x = 3 \Rightarrow x^2 = 9$. The reverse fails, because $x^2 = 9$ is also true for $x = -3$. So $x^2 = 9$ does not imply $x = 3$. When you solve an equation and each line follows from the last in both directions, you can write $\Leftrightarrow$; squaring both sides is a typical step where only $\Rightarrow$ is safe and false solutions can appear.

The symbol $\equiv$ means "is identically equal to": the two sides are equal for every value of the variable, as in $(x+1)^2 \equiv x^2 + 2x + 1$. It differs from $=$, which asks for particular values of $x$.

Proof by deduction

Proof by deduction is the direct method. Begin with known facts or definitions, manipulate algebraically, and arrive at the claim. For statements about a whole class of numbers, represent the class algebraically. An even number is $2n$ for an integer $n$, and an odd number is $2n+1$. Consecutive integers are $n$ and $n+1$.

Worked example

Prove that the sum of the squares of two consecutive integers is always odd.

Let the integers be $n$ and $n+1$. Then

Since $n^2 + n$ is an integer, this has the form $2k + 1$ with $k$ an integer, so it is odd. The argument works for every integer $n$, which is what makes it a proof.

Proving inequalities and identities

To prove an identity, start from one side and transform it into the other, or reduce both sides to the same expression. To prove an inequality, it is often enough to rewrite the difference as something known to be non-negative, such as a square.

For example, to show $a^2 + b^2 \ge 2ab$ for all real $a$ and $b$, consider the difference:

A square of a real number is never negative, so the difference is non-negative and the inequality holds for all real $a$ and $b$.

Proof by exhaustion

Proof by exhaustion splits the possibilities into a finite number of cases and checks each one. It is only practical when the cases are few, or when a general argument can cover each case at once.

To show that $n^3 - n$ is divisible by 3 for every integer $n$, note that every integer is of the form $3k$, $3k+1$ or $3k+2$. Factorising first gives $n^3 - n = (n-1)n(n+1)$, which is the product of three consecutive integers. In each case one of the three factors is a multiple of 3:

• if $n = 3k$, then $n$ is a multiple of 3;
• if $n = 3k + 1$, then $n - 1 = 3k$ is a multiple of 3;
• if $n = 3k + 2$, then $n + 1 = 3k + 3 = 3(k+1)$ is a multiple of 3.

All cases are covered, so the product is always divisible by 3.

A statement about the integers from 1 to 10 can be proved by exhaustion by testing each of them. A statement about all integers cannot, unless the cases are grouped as above.

Disproof by counter-example

To show that a statement of the form "if $P(x)$ is true then $Q(x)$ is true" is false, it is enough to find one value of $x$ for which $P(x)$ is true and $Q(x)$ is false. That single value is a counter-example.

The claim "$n^2 + n + 11$ is prime for every positive integer $n$" is true for $n = 1, 2, \dots, 9$, which might make it look convincing. At $n = 10$ the value is $100 + 10 + 11 = 121 = 11^2$, which is not prime. One failure settles it.

A counter-example has to satisfy the conditions of the statement. To disprove "the square of any number is greater than the number itself", the value $x = 0.5$ works since $0.25 < 0.5$, and so does $x = 1$ since $1 = 1$ is not greater. A value such as $x = -2$ would not help, because $4 > -2$ and the statement holds there.

Proof by contradiction

In proof by contradiction, assume the statement is false, then show that this assumption leads to something impossible (a contradiction of a known fact or of the assumption itself). The only way out is that the assumption was wrong, so the statement is true.

The irrationality of $\sqrt{2}$

Assume $\sqrt{2}$ is rational. Then $\sqrt{2} = \dfrac{p}{q}$ where $p$ and $q$ are integers with no common factor, which is always possible by cancelling any common factors.

So $p^2$ is even, which means $p$ is even (the square of an odd number is odd). Write $p = 2m$. Then $4m^2 = 2q^2$, so $q^2 = 2m^2$ and $q^2$ is even, so $q$ is even too.

Now $p$ and $q$ are both even, so they share the factor 2. That contradicts the assumption that they have no common factor. Therefore $\sqrt{2}$ cannot be rational, and is irrational.

The same pattern shows that $\sqrt{3}$ is irrational, using "a square divisible by 3 forces the number to be divisible by 3".

There are infinitely many primes

Assume there are only finitely many primes and list them all: $p_1, p_2, \dots, p_n$. Form the number

Dividing $N$ by any $p_i$ leaves remainder 1, so no prime on the list divides $N$. But every integer greater than 1 is either prime or has a prime factor. If $N$ is prime it is not on the list, and if it is composite it has a prime factor that is not on the list. Either way the list was incomplete, which contradicts the assumption. So the primes do not run out.

Another example

Prove that there is no smallest positive rational number. Suppose $r$ is the smallest one. Then $\dfrac{r}{2}$ is also rational and positive, and $\dfrac{r}{2} < r$. This contradicts the choice of $r$, so no smallest positive rational exists.

Choosing a method

A full proof states its assumptions, sets out every step, and ends by saying what has been shown. Setting $n$ to be a specific number, or checking a few cases, is evidence but not proof.