Proof by deduction and exhaustion
Studying this course? Keep your progress in one place.
Key facts
- A proof must work for every case, not just examples; examples cannot prove a statement.
- Even number , odd number , consecutive integers .
- Use different letters for independent integers, such as and .
- Exhaustion splits the possibilities into finite cases, proves each, and shows the cases cover everything.
- To show a multiple of , aim for ; to show odd, aim for .
The structure of a proof
A proof moves from stated assumptions through justified steps to a conclusion that covers every case.
A proof starts from stated assumptions or known facts and moves through logical steps, each justified, to a conclusion.
It must work for every case covered by the statement, not just examples you have tried.
This subtopic uses two methods: proof by deduction and proof by exhaustion.
- 1
Define symbols
for example "let be an integer"
- 2
Reason in steps
connect lines with , , "so" or "hence"
- 3
Conclude
link back to the question, such as "so the sum is odd"
Does checking that a statement works for prove it for all integers?
Proof by deduction
Represent the numbers algebraically, manipulate them, and show the result has the required form.
In proof by deduction you start from known facts and use algebra to reach the result for all values at once.
With and integers: even is , odd is , consecutive odd numbers are and , a multiple of 3 is .
Use different letters for independent integers, such as and for two even numbers.
- 1
Represent with algebra
even 2n, odd 2n + 1, consecutive n, n + 1, n + 2
- 2
Manipulate
expand and factorise
- 3
Show the form of the claim
k(…) for a multiple of k, 2(…) + 1 for odd
- 4
State the conclusion
it holds for every integer n
- Even number
- Odd number
- Consecutive integers
Worked example
Prove that the sum of three consecutive integers is a multiple of 3.
- 1
Let the integers be , and .
- 2
Their sum is .
- 3
Factorise: .
- 4
Since is an integer, the sum is times an integer.
Worked example
Show that is always even.
- 1
Factorise: .
- 2
This is a product of consecutive integers, so one of the two factors is even.
Which expression represents any odd number, for integer ?
Proof by exhaustion
Split the possibilities into a finite number of cases, prove each, and show the cases cover everything.
In proof by exhaustion you check every one of a finite number of cases. Each integer has a remainder when divided by 3, so every integer is , or .
The last digit of depends only on the last digit of , because gives . Checking shows no square ends in , , or .
Squares modulo 3, using the three cases:
So every square is or for some integer .
Can a square number end in 7?
Combining the methods
Factorise first (deduction), then split into cases (exhaustion) to show a divisibility result.
Many proofs use both methods. To prove is divisible by 6, factorise first, then split into cases.
For a sum or product claim, rewrite the result in the form of a multiple, then say why that proves the statement. To show something is odd, aim for ; to show it is a multiple of , aim for .
- 1
Factorise
n³ − n = (n − 1)n(n + 1)
- 2
Deduction: divisible by 2
three consecutive integers include an even number
- 3
Exhaustion: divisible by 3
n = 3k, 3k + 1 or 3k + 2 each give a multiple of 3
- 4
Combine
2 and 3 share no factor, so it is divisible by 6
Deduction
- Algebra from known facts
- Covers all values at once
Exhaustion
- Split into finite cases
- Prove each case and show the cases cover everything
Worked example
Prove that is divisible by 6 for every integer .
- 1
Deduction: , three consecutive integers.
- 2
At least one is even, so the product is divisible by 2.
- 3
Exhaustion: if , or , then , or 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.
Why is always divisible by 3?
Try an exam question
Prove that the sum of two consecutive odd numbers is a multiple of .
[3 marks]
- [1]Let the consecutive odd numbers be and , where is an integer.
- [1]Their sum is .
- [1] is times an integer, so the sum is a multiple of .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which expression is always even?
1 mark, marked against the mark scheme
Which expression is always even?
1 mark, marked against the mark scheme