Proof by deduction and exhaustionAQA A-Level Maths: Revision notes

A proof starts from stated assumptions or known facts and moves through logical steps, each justified, to a conclusion. A proof must work for every case covered by the statement, not just examples you have tried. Good presentation:

• define your symbols (for example "let $n$ be an integer");
• connect lines with $\Rightarrow$ or $\Leftrightarrow$, or "so" and "hence";
• end with a clear statement that links back to the question, such as "so the sum is odd". This subtopic uses two methods: proof by deduction and proof by exhaustion.

In proof by deduction you start from known facts and use algebra to reach the result for all values at once. Standard representations, with $n$ and $m$ integers:

• even number: $2n$; odd number: $2n+1$;
• consecutive integers: $n$, $n+1$, $n+2$; consecutive odd numbers: $2n-1$, $2n+1$;
• multiple of 3: $3n$; one more than a multiple of 3: $3n+1$. Use different letters for independent integers, such as $2m$ and $2n$ for two even numbers. Worked example: prove the sum of three consecutive integers is a multiple of 3. $n+(n+1)+(n+2)=3n+3=3(n+1).$ Since $n+1$ is an integer, the sum is a multiple of 3. Worked example: show $n^2+n$ is always even. $n^2+n=n(n+1)$, a product of consecutive integers, so one factor is even.

In proof by exhaustion you split the possibilities into a finite number of cases, prove the statement in each, and show that the cases cover everything. Example: every integer is $3k$, $3k+1$ or $3k+2$. Then $(3k)^2=3(3k^2),\quad(3k+1)^2=3(3k^2+2k)+1,\quad(3k+2)^2=3(3k^2+4k+1)+1.$ So every square is $3m$ or $3m+1$ for some integer $m$. Example with digits: the last digit of $n^2$ depends only on the last digit $d$ of $n$, because $n=10k+d$ gives $n^2=10(10k^2+2kd)+d^2$. Checking $d=0,\ldots,9$ gives last digits $0,1,4,9,6,5,6,9,4,1$, so no square ends in $2,3,7$ or $8$. Exhaustion only works when the number of cases is finite and each is covered.

Many proofs use both. To prove $n^3-n$ is divisible by 6:

1. Deduction: $n^3-n=(n-1)n(n+1)$, three consecutive integers.
2. At least one is even, so the product is divisible by 2.
3. Exhaustion: if $n=3k$, $3k+1$ or $3k+2$, then $n$, $n-1$ or $n+1$ respectively is a multiple of 3, so the product is divisible by 3.
4. Since 2 and 3 have no common factor, the product is divisible by 6. Finish by saying what has been proved. For a sum or product claim, factorise or rewrite the result in the form of a multiple, then say why that proves the statement.