Proof by deduction, exhaustion and counter-example
Studying this course? Keep your progress in one place.
Key facts
- A proof runs from assumptions through logical steps to a conclusion stated in words. Testing examples is not a proof.
- Deduction: use algebra to prove a result for all cases at once. Even is , odd is .
- Exhaustion: split into a finite number of cases and check every one.
- To disprove a statement you need only one counter-example.
- Use deduction for all integers or reals, exhaustion for a finite list, a counter-example to disprove.
The structure of a proof
A proof starts from assumptions, takes logical steps where each follows from the one before, and ends with a conclusion in words.
A proof starts from given assumptions, moves through logical steps and ends with a conclusion.
Each step must follow from the one before, and the last line should say what has been proved, such as "so the sum is always odd". Use for "implies" and when the reasoning works both ways.
Testing a few values is not a proof. A proof must work for every case the statement covers. AS needs deduction, exhaustion and disproof by counter-example.
- 1
Assumptions
what you are given or may take as true
- 2
Logical steps
each line follows from the one before
- 3
Conclusion
say in words what has been proved
Which is a valid proof that is positive for all real ?
Proof by deduction
Start from known facts and use algebra to reach the result for all cases at once, ending with a sentence linking back to the claim.
In proof by deduction you start from known facts and use algebra to reach the result for all cases at once.
- Completing the square: , so it is positive for all real .
- Divisibility: show the expression equals the divisor times an integer, such as where is even, so the result is a multiple of 4.
Use a different letter for each independent integer, such as and . End with a sentence linking back to the claim.
- Even integer
- Odd integer
- Consecutive integers and
Worked example
Prove that the sum of the squares of two consecutive integers is always odd.
- 1
Let the integers be and .
- 2
Sum of squares: .
- 3
Factorise: .
- 4
is an integer, so is even and the expression is even plus 1.
Which expression always represents an odd integer, for integer ?
Deduction with calculus and series
Standard results, such as differentiation from first principles and series sums, are proved by the same method.
The same method proves standard results.
Arithmetic series. Write and reverse it. Adding the two lines gives , so .
Geometric series. and . Subtracting gives , so .
Dividing by needs .
- 1
Write the series
- 2
Multiply by r
- 3
Subtract
- 4
Factorise and divide
for
Worked example
Prove from first principles that the derivative of is .
- 1
Gradient of the chord: .
- 2
Expand: .
- 3
Let : .
Why does the geometric series proof need ?
Proof by exhaustion
Split the possibilities into a finite number of cases and show the statement is true for every one.
In proof by exhaustion you split the possibilities into a finite number of cases and show the statement is true for every case.
Example: prove is a multiple of 12 for primes . The primes are 5, 7, 11, 13, 17, 19, 23, and the chart shows each value divided by 12.
You must (1) list all the cases with none missing, (2) check each, and (3) conclude. It works when the cases are finite or can be reduced to a finite number, such as even and odd.
To prove is even for every integer using exhaustion, which cases do you consider?
Disproof by counter-example
One counter-example is enough: a value that satisfies the conditions but fails the claim.
To show a statement is false you need only one counter-example: a single value that satisfies the conditions but fails the claim.
Example: "for all , is prime" is untrue because gives .
To prove a statement true you need a general argument. Many examples that work prove nothing: is prime for , but gives .
| To prove true | To disprove | |
|---|---|---|
| You need | A general argument | One counter-example |
| Note | Many examples are not enough | Check it carefully and say why it fails |
To prove true
- You need:
- A general argument
- Note:
- Many examples are not enough
To disprove
- You need:
- One counter-example
- Note:
- Check it carefully and say why it fails
Worked example
Disprove: "for all positive integers , is prime".
- 1
Try small values: gives 3, gives 7, gives 13, all prime.
- 2
Keep going: gives .
- 3
Factorise: , so it is not prime.
Which value is a counter-example to "for all positive integers , "?
Choosing a method
Use deduction for all integers or reals, exhaustion for a finite list, and a counter-example for a claim you think is false.
A good write-up states the assumptions, shows each logical step, and ends with a conclusion in words. Use ("therefore") or "hence" to show how lines follow.
If the question says "prove", give a general argument. If it says "show that" with specific numbers, you are checking a particular case.
| Deduction | Exhaustion | Counter-example | |
|---|---|---|---|
| Use when | All integers or all real numbers | A finite list of cases | A claim you think is false |
| Example | primes below 25 | for |
Deduction
- Use when:
- All integers or all real numbers
- Example:
Exhaustion
- Use when:
- A finite list of cases
- Example:
- primes below 25
Counter-example
- Use when:
- A claim you think is false
- Example:
- for
Which method suits "prove that for all real "?
Try an exam question
(a) Prove that the sum of any three consecutive integers is a multiple of 3. (b) Give a counter-example to the statement "the sum of any four consecutive integers is a multiple of 4".
[4 marks]
- [1]Let the integers be , and .
- [1]Sum , a multiple of 3 because is an integer.
- [1]Counter-example: .
- [1]10 is not a multiple of 4, so the statement is false.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which value of is a counter-example to the claim?
1 mark, marked against the mark scheme
Which value of is a counter-example to the claim?
1 mark, marked against the mark scheme