Structure of proof and proof by exhaustion
Studying this course? Keep your progress in one place.
Key facts
- A proof runs from assumptions through justified steps to a clear conclusion.
- A few examples that agree with a statement do not prove it.
- Proof by exhaustion checks every possible case, so it needs a finite number of cases.
- List every case, check each one, then conclude in words.
- It cannot prove a statement about all integers.
What a proof is
A proof is a logical argument from given assumptions, through justified steps, to a conclusion that matches the claim.
State what is proved and the numbers it applies to, state any assumptions, show each step, and finish with a conclusion in words that links back to the claim.
To prove a statement for a set of cases, you must deal with every case in the set.
- 1
State the claim
and the numbers it applies to
- 2
Assumptions
state what you are given or using
- 3
Logical steps
each one justified
- 4
Conclusion
in words, matching the claim
Three examples agree with a statement. Is it proved?
Proof by exhaustion
Check every possible case and show the statement is true in each; this works only for a finite number of cases.
List every case allowed by the conditions, check each, and conclude that the statement is true because it holds in every case.
If even one case fails, the statement is false, and the failing case shows why.
- 1
List every case
allowed by the conditions
- 2
Check each case
show the working
- 3
Conclude
true because it holds in every case
When can proof by exhaustion be used?
Example: sums of odd integers
List every pair, work out each sum, and conclude that all are divisible by .
Because , you may list each unordered pair once, but say that you are doing so.
| Sum | Divisible by 2? | |
|---|---|---|
| and | 2 | Yes |
| and | 4 | Yes |
| and | 6 | Yes |
| and | 6 | Yes |
| and | 8 | Yes |
| and | 10 | Yes |
Sum
- and :
- 2
- and :
- 4
- and :
- 6
- and :
- 6
- and :
- 8
- and :
- 10
Divisible by 2?
- and :
- Yes
- and :
- Yes
- and :
- Yes
- and :
- Yes
- and :
- Yes
- and :
- Yes
Worked example
Prove that if and are odd positive integers less than , then is divisible by .
- 1
The only possible values of each of and are .
- 2
The possible sums are , , , , , .
- 3
Each sum is divisible by .
How many unordered pairs are there when ?
Example: evaluating an expression
Set out a table showing the calculation for each case, then state the conclusion in context.
Show the working for each case, not just the answer. This convinces the examiner that every case has been done.
| Even? | ||
|---|---|---|
| 2 | Yes | |
| 6 | Yes | |
| 12 | Yes | |
| 20 | Yes | |
| 30 | Yes |
- :
- 2
- :
- 6
- :
- 12
- :
- 20
- :
- 30
Even?
- :
- Yes
- :
- Yes
- :
- Yes
- :
- Yes
- :
- Yes
Worked example
Prove that for every integer with , is even.
- 1
Work out for each value: , , , , .
- 2
All five values are even.
What is when ?
Limits of exhaustion
It cannot prove a statement about all integers: there are infinitely many cases and you cannot check them all.
Checking shows is a multiple of for those values only. It says nothing about .
A single failing case is enough to show a statement false: is prime for , but gives .
Can prove
- A finite list of cases
- Every case is checked
Cannot prove
- All integers
- Infinitely many cases
is prime for to . What does show?
Try an exam question
Prove, by exhaustion, that is divisible by for every integer with .
[4 marks]
- [1]Lists the cases .
- [1]Evaluates correctly: , , , .
- [1]Shows each is a multiple of : , , , .
- [1]Concludes that, since every case works, the statement is true for .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which of the following is needed for a proof by exhaustion of S?
1 mark, marked against the mark scheme
Which of the following is needed for a proof by exhaustion of S?
1 mark, marked against the mark scheme