A proof is a chain of logical steps that shows a statement is true for every case, not just the ones you tried. This note covers numerical and algebraic proofs, laying out a left-hand side to right-hand side argument, and the notation for equality and identity. It builds the habit of explaining why a result is true, which you will use throughout the course.
Key ideas
Testing a few numbers can suggest that a statement is true, but it cannot prove it. A deductive proof starts from facts that are already known (definitions, rules of algebra) and reaches the conclusion by steps that each follow logically from the one before. If the starting facts are true and every step is valid, the conclusion must be true for all cases covered.
On the other hand, one example that fails is enough to show that a statement is false. Such an example is called a counterexample. For instance, the claim "\(n^2 + n + 11\) is prime for every positive integer \(n\)" is false, because for \(n = 11\) we get \(121 + 11 + 11 = 143 = 11 \times 13\).
Representing types of number. To prove statements about whole numbers in general, use letters for them.
- An even number can be written \(2n\), where \(n\) is an integer.
- An odd number can be written \(2n+1\) (or \(2n-1\)), where \(n\) is an integer.
- Two consecutive integers are \(n\) and \(n+1\).
- A multiple of \(k\) can be written \(k \times (\text{an integer})\).
If you need two different even numbers, use different letters, such as \(2a\) and \(2b\). Using the same letter for both would force them to be equal, which is not general enough.
Showing a result is a multiple. To prove that an expression is a multiple of \(k\), expand and simplify it until you can factorise \(k\) out. The final line should be \(k\) times a whole number expression, and you should say that this expression is an integer.
Notation. The symbol \(=\) is used for an equation, which is true only for certain values of the variable, such as \(x + 3 = 7\). The symbol \(\equiv\) is used for an identity, which is true for all values of the variable, such as \((x+1)^2 \equiv x^2 + 2x + 1\). Other helpful symbols are \(\Rightarrow\) ("implies") and \(\therefore\) ("therefore"). At the end of a proof, you may write "as required", or the letters QED, to signal that you have reached what was to be shown.
Left-hand side to right-hand side layout. To prove an identity, start with one side (usually the more complicated one) and use algebra to turn it into the other side. Write each step on a new line with an equals sign. Do not start by writing the whole claim and working on both sides at once, because you would be assuming what you want to prove. Keep the other side visible and finish with the exact form given.
Definitions and formulae
| Term or formula | Meaning / when to use |
|---|---|
| \(2n\) | General even integer, for integer \(n\). |
| \(2n+1\) | General odd integer. |
| \(n,\ n+1\) | Two consecutive integers. |
| \(=\) and \(\equiv\) | Equation (true for some values) and identity (true for all values). |
| \(\Rightarrow\) | "Implies": the next statement follows from the last. |
| Counterexample | A single case that shows a general claim is false. |
Worked examples
Example 1 Prove that the sum of any three consecutive integers is a multiple of 3.
Let the three consecutive integers be \(n\), \(n+1\) and \(n+2\), where \(n\) is an integer.
Sum \(= n + (n+1) + (n+2) = 3n + 3 = 3(n+1)\).
Since \(n+1\) is an integer, \(3(n+1)\) is a multiple of 3.
Therefore the sum of any three consecutive integers is a multiple of 3, as required.
Example 2 Show that \((2x+1)^2 - (2x-1)^2 \equiv 8x\).
Start with the left-hand side and expand each bracket.
\((2x+1)^2 = 4x^2 + 4x + 1\) and \((2x-1)^2 = 4x^2 - 4x + 1\).
LHS \(= (4x^2 + 4x + 1) - (4x^2 - 4x + 1)\)
\(= 4x^2 + 4x + 1 - 4x^2 + 4x - 1\)
\(= 8x\) = RHS.
Therefore \((2x+1)^2 - (2x-1)^2 \equiv 8x\), as required.
Example 3 (a) Prove that the product of two odd integers is odd. (b) Show that \(7^{12} - 7^{10}\) is divisible by 48.
(a) Let the two odd integers be \(2a+1\) and \(2b+1\), where \(a\) and \(b\) are integers.
Product \(= (2a+1)(2b+1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1\).
Since \(2ab + a + b\) is an integer, the product has the form \(2m + 1\), so it is odd.
(b) Factorise using the lower power: \(7^{12} - 7^{10} = 7^{10}(7^2 - 1) = 7^{10} \times 48\).
This is 48 multiplied by the integer \(7^{10}\), so \(7^{12} - 7^{10}\) is divisible by 48.
Common errors
- Common error: "proving" a general statement by checking a few numbers. Examples support a claim but do not prove it.
- Common error: using the same letter for two different integers, such as writing two odd numbers both as \(2n+1\).
- Common error: working on both sides of an identity at once, which assumes the result. Work on one side and arrive at the other.
- Common error: stopping without a conclusion. The last line should say what has been shown and why, for example that an expression is \(2\) times an integer, or \(k\) times an integer.
- Common error: confusing \(=\) with \(\equiv\). An identity holds for all values, not only for those that solve an equation.
Exam tip: End every proof with a short sentence that states why the final form proves the claim, such as "this is \(3\) times an integer, so it is a multiple of \(3\)".
Check yourself
- Prove that the sum of two even integers is even.
Answer
Let the integers be \(2a\) and \(2b\). Their sum is \(2a + 2b = 2(a+b)\). Since \(a+b\) is an integer, the sum is even. - Prove that \((n+2)^2 - n^2\) is a multiple of 4 for every integer \(n\).
Answer
\((n+2)^2 - n^2 = n^2 + 4n + 4 - n^2 = 4n + 4 = 4(n+1)\). Since \(n+1\) is an integer, the result is a multiple of 4. - Prove that the sum of the squares of two consecutive integers is odd.
Answer
\(n^2 + (n+1)^2 = 2n^2 + 2n + 1 = 2(n^2+n) + 1\). Since \(n^2 + n\) is an integer, this has the form \(2m+1\), so it is odd. - Find a counterexample to the claim "\(n^2 \gt n\) for every integer \(n\)".
Answer
Take \(n = 1\): \(1^2 = 1\), which is not greater than 1. (\(n = 0\) also works.) One counterexample shows the claim is false.