Proof by Exhaustion
Maths: Edexcel A Level Pure Maths, topic 1.3.5
What is Proof by Exhaustion?
Proof by exhaustion is a method of proving that a mathematical statement is always true by working it out and showing it is true for every possible case.
How do you prove by exhaustion?
- To prove a conjecture by exhaustion, split it up into different cases.
- The different cases come from looking at all of the possible values within the range that the conjecture is true for.
Example
- Prove that no square number ends in a 7.
- It's impossible to write out all the square numbers to show that they don't end in a 7.
- We have to think of another way to cover all of the possible cases.
What are the different cases?
- All numbers ending in the same digits have square numbers that also end in the same digits.
- For example. as 42 = 16, all numbers ending in 4 will have square numbers that end in 6.
- This is a known theorem, so we can begin our proof with this statement.
- So the cases to consider are the squares of the 10 different digits that a number can end in.
Square numbers
- Writing out the square numbers, we have:
- 02 = 0, 12 = 1, 22 = 4
- 32 = 9, 42 = 16, 52 = 25
- 62 = 36, 72 = 49, 82 = 64 and 92 = 81
Inspection
- We see the possible digits they can end in are:
- The number 7 is missing from this list.
Final statement
- No square number can end in a 7.
Full proof
Test yourself on Proof by Exhaustion
Which type of proof requires you to consider all possible cases independently to prove conjecture is true?