Maths › Proof › The structure of proof: deduction and exhaustion
The structure of proof: deduction and exhaustion
Mathematical proof establishes a statement for every case it covers. Use implication, equivalence, necessary and sufficient conditions, proof by deduction and proof by exhaustion, and distinguish proof from checking examples.
IN THIS TOPIC
- Set a proof out properly, from stated assumptions through checkable steps to a conclusion.
- Read and write the implication and equivalence arrows, and tell a statement apart from its converse.
- Prove statements by deduction and by exhaustion, and choose the method that suits the claim.
COMMON MISCONCEPTION
Checking a statement for the first few numbers proves it.
Checking examples settles those examples only. A proof starts from given assumptions, moves through logical steps anybody can check, and ends at a conclusion that holds in every case the claim covers. Algebraic naming is what makes that possible: write any odd number as 2n + 1, argue about the letter, and one argument covers the whole family.
What counts as a proof
Try a claim on a handful of numbers and it may work every time. That is evidence, not proof. A proof starts from given assumptions, things already agreed, moves through logical steps that anybody can check, and ends at a conclusion that must then hold in every case the claim covers, however many there are.
What makes a general argument possible is algebraic naming. Any even number is 2n for some integer n, and any odd number is 2n + 1. Consecutive integers are n and n + 1. Name the family, argue about the letter, and every member of the family is covered by the one argument. Proof by deduction and proof by exhaustion are the two methods required by Edexcel 9MA0 1.1, and a question may ask you to select between them.
Implication and equivalence
A proof is a chain of claims about what forces what, and the links have a notation of their own. P ⇒ Q, read aloud as “P implies Q” or “if P then Q”, says that wherever P holds, Q holds with it. It says nothing about the case where P fails, and nothing about whether Q might hold for some quite different reason. A deduction is a run of those arrows: each one is a step somebody can check, and the run from the assumptions to the conclusion is the proof.
Reverse the arrow and you have a different statement, the converse, Q ⇒ P, which needs a proof of its own, because a true claim can have a false converse. “If n is a multiple of 4 then n is even” holds. Its converse, “if n is even then n is a multiple of 4”, fails at n = 6. The converse may also be written P ⇐ Q, with the arrow pointing back at P; it means the same as Q ⇒ P. A proof of P ⇒ Q does not establish Q ⇒ P, so the arrow you write must point the way you have argued.
When both directions do hold, the two statements are equivalent, written P ⇔ Q and read as “P if and only if Q”, shortened in writing to “iff”. The double-headed arrow is two claims in one symbol, so a proof of an equivalence is two proofs: assume P and derive Q, then assume Q and derive P. One direction alone proves only half of the equivalence. The factor theorem and the definition of a logarithm are both written with that arrow later in the course, and in each case it is claiming both directions at once.
Questions ask for the same idea in words. If P ⇒ Q then P is a sufficient condition for Q, enough on its own to force it, and Q is a necessary condition for P, unavoidable if P is to hold at all. Being a multiple of 4 is sufficient for being even but not necessary; being even is necessary for being a multiple of 4 but not sufficient. A condition stated as necessary and sufficient is an equivalence, so both directions must be proved.
Proof by deduction
Deduction argues in general. A common technique is completing the square, and a standard example asks you to show that n2 − 6n + 10 is positive for every value of n.
WORKED EXAMPLE
Always positive, in two lines
Prove that n2 − 6n + 10 > 0 for all values of n.
Complete the square. n2 − 6n + 10 = (n − 3)2 + 1.
A square is never negative, so (n − 3)2 ≥ 0, and (n − 3)2 + 1 is therefore at least 1. ∎
Rewriting the expression made its sign visible. No numerical value was tested, and the argument covers every value of n, negatives and fractions included.
GUIDED PRACTICE
Odd times odd
Prove that the product of any two odd numbers is odd, before opening the working.
Show the working
Name the family. Two odd numbers can be written 2m + 1 and 2n + 1 for integers m and n.
(2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1.
That is 2 × (an integer) + 1, which is what odd means. ∎ The argument is one expansion and one regrouping; naming the two odd numbers algebraically is what makes it general.
Proof by exhaustion
Some claims cover only finitely many cases, and then every case can be checked directly. Proof by exhaustion checks each case in a list. It is valid only when the list is complete, so state why the list covers every possible case.
WORKED EXAMPLE
Every prime between 3 and 25
Given that p is a prime number with 3 < p < 25, prove by exhaustion that (p − 1)(p + 1) is a multiple of 12.
The primes strictly between 3 and 25 are 5, 7, 11, 13, 17, 19 and 23, and there are no others.
Taking each in turn, (p − 1)(p + 1) comes out as 24, 48, 120, 168, 288, 360 and 528.
Dividing those by 12 gives 2, 4, 10, 14, 24, 30 and 44, all whole. Every case in the complete list has been checked. ∎
Exhaustion does not need the cases to be individual numbers. Split the integers into types, even and odd being the usual pair, then deal with each type generally. That is still exhaustion, and it proves a statement about all the integers when a single algebraic form does not cover them.
INDEPENDENT PRACTICE
Squares, sorted by remainder
Prove that every square number is either a multiple of 4 or one more than a multiple of 4.
Show the working
Every integer is even or odd, and those two cases exhaust the possibilities.
Even. (2n)2 = 4n2, a multiple of 4.
Odd. (2n + 1)2 = 4n2 + 4n + 1 = 4(n2 + n) + 1, one more than a multiple of 4. ∎
A proof may combine methods. In this example, deduction deals with each case and exhaustion shows that the cases cover every integer. State why the cases are exhaustive.
ASSESSMENT FOCUS
- State the algebraic family before using it: "Let the numbers be 2m + 1 and 2n + 1, where m and n are integers". Without that line the working refers to no defined quantities.
- A claim that a quadratic is always positive or always negative is proved by completing the square. A square term plus a positive constant fixes the sign for every value of the variable.
- Choose the method from the form of the claim. A finite set of cases can be settled by exhaustion, provided the list is shown to be complete; a claim about all the integers or all the reals needs a general deduction.
- A question that states P ⇒ Q and asks whether the converse holds requires a counter example to Q ⇒ P. A question asking for a necessary and sufficient condition requires both directions to be proved.
- Finish with a conclusion stated in the terms of the claim. A complete answer includes that sentence as well as the algebra.
CHECK YOURSELF
Prove that n³ − n is divisible by 6 for every integer n.
Show a hint
Factorise first, then think about what three consecutive integers must contain.
Show the answer
Factorise. n3 − n = n(n2 − 1) = (n − 1)n(n + 1), the product of three consecutive integers.
Any run of three consecutive integers contains at least one even number, so the product is divisible by 2, and exactly one multiple of 3, so the product is divisible by 3.
Divisible by 2 and by 3 means divisible by 6. ∎ The argument is a deduction from one factorisation and two properties of consecutive integers.
A proof runs from stated assumptions through checkable steps to a conclusion, and establishes it for every case the claim covers.
P ⇒ Q claims one direction; P ⇔ Q claims both, so an equivalence takes two proofs.
Use deduction for a general argument, and exhaustion when a complete list of cases can be checked.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the structure of proof: deduction and exhaustion questions page.
USED LATER IN
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Set a proof out properly, from stated assumptions through checkable steps to a conclusion.
- Read and write the implication and equivalence arrows, and tell a statement apart from its converse.
- Prove statements by deduction and by exhaustion, and choose the method that suits the claim.
Open the full revision checklist to see every objective in the course in one place.