Proof by deduction, exhaustion and counter-exampleEdexcel A-Level Maths: Revision notes

A proof starts from given assumptions, moves through a series of logical steps and ends with a conclusion. Each step must follow from the one before, and the last line should state what has been proved, for example 'so the sum is always odd'. Use $\Rightarrow$ for 'implies' and $\Leftrightarrow$ when the reasoning works in both directions. Testing a few values is not a proof. It can suggest a result, but a proof must work for every case covered by the statement. Three methods are needed at AS: deduction, exhaustion and disproof by counter-example.

In proof by deduction you start from known facts and use algebra to reach the result for all cases at once.

• Even and odd: an even integer is $2k$ and an odd integer is $2k+1$. Consecutive integers are $n$ and $n+1$. The sum of the squares of two consecutive integers is $n^2+(n+1)^2=2(n^2+n)+1$, which is always odd.
• Completing the square: $n^2-6n+10=(n-3)^2+1$. Since $(n-3)^2\geqslant0$, the expression is at least 1, so it is positive for all real $n$.
• Divisibility: show the expression equals the divisor multiplied by an integer, for example $2n(n+1)$ where $n(n+1)$ is even, so the result is a multiple of 4. End with a sentence linking back to the claim, such as 'so the expression is a multiple of 4 for every integer $n$'.

The same method proves standard results. First principles. For $f(x)=x^2$: $\frac{f(x+h)-f(x)}{h}=\frac{2xh+h^2}{h}=2x+h\to2x$ as $h\to0$, so $f'(x)=2x$. Arithmetic series. Write $S=a+(a+d)+\cdots+l$ and reverse it. Adding the two lines gives $2S=n(a+l)$, so $S=\frac{n}{2}(a+l)=\frac{n}{2}\left(2a+(n-1)d\right)$. Geometric series. $S_n=a+ar+\cdots+ar^{n-1}$ and $rS_n=ar+\cdots+ar^n$. Subtracting gives $(1-r)S_n=a(1-r^n)$, so $S_n=\frac{a(1-r^n)}{1-r}$ for $r\neq1$.

In proof by exhaustion you split the possibilities into a finite number of cases and show the statement is true for every case. Example: prove $(p-1)(p+1)$ is a multiple of 12 for primes $3<p<25$. The primes are $5,7,11,13,17,19,23$, and the values $24,48,120,168,288,360,528$ are $12\times2,\ 12\times4,\ 12\times10,\ 12\times14,\ 12\times24,\ 12\times30,\ 12\times44$. To use exhaustion you must (1) list all the cases with none missing, (2) check each one, and (3) conclude. It only works when the number of cases is finite, or can be reduced to a finite number, for example by considering $n$ even and $n$ odd.

To show a statement is false you only need one counter-example: a single value that satisfies the conditions but fails the claim. Example: 'for all $n$, $n^2-n+1$ is prime' is untrue because $n=5$ gives $25-5+1=21=3\times7$, which is not prime. Check the counter-example carefully and state clearly why it fails. In contrast, to prove a statement true you need a general argument. Finding many examples that work does not prove it. For instance $n^2+n+41$ is prime for $n=1,\ldots,39$ but $n=40$ gives $1681=41^2$.

• Statement about all integers or all real numbers: deduction (algebra).
• Finite list of possibilities, such as primes below 25: exhaustion.
• Statement claimed true that you think is false: look for a counter-example. A good write-up states the assumptions, shows each logical step, and ends with a conclusion in words. Use $\therefore$ ('therefore') or 'hence' to show how lines follow.