Lesson 6 of 8 · 18 min
Proof by cases and by contrapositive
Prove results for every integer by splitting into cases such as odd and even, and prove an implication by proving its contrapositive instead.
What you will be able to do
- Prove a result for all by considering even and odd, or , , .
- Prove is even for all .
- Prove by proving , for example "if is even then is even".
Try for a few integers: gives 6, gives 14, gives 32, gives 42. Always even. But writing as one general expression does not help here, because an even and an odd make the expression even for different reasons. So split the integers into cases and prove each one.
Key idea
Proof by cases
If every possibility falls into one of a few cases, prove the result in each case separately. The cases must cover every possibility.
- Every integer is even or odd: or , .
- Every integer leaves remainder 0, 1 or 2 on division by 3: , or .
Worked example
is always even
Prove that is even for all .
Step 1: Set up the cases
Every integer is either even or odd, so consider and , where .
The two cases cover all of , so proving both proves the statement for every integer.
Step 2: Case 1: n even
Step 3: Case 2: n odd
Step 4: Conclude
In both cases the bracket is an integer, since , so is a multiple of 2. Hence is even for all .
Try it yourself first, then check the working one step at a time.
Answer
In both cases ( and ) the expression is 2 times an integer, so it is even for every integer .
Method
State the cases and why they cover every integer.
Substitute and simplify in each case.
Factor out 2 and say the bracket is an integer.
Conclude for all integers.
Watch out for
Expanding as .
Proving only one case.
By cases
Substitute and and show each result has a factor of 2. Reliable and systematic, but more algebra.
By factorising
. If is even, is even; if is odd, is odd + odd, which is even. Either way is even, and even + 6 is even. Shorter, but it still uses the two cases.
For , which statement about is true?
Every integer is exactly one of , or . These three cases cover all of , so they can be used for a proof by cases.
Let , where . Then for some and . Find .
Proof using the contrapositive. Try to prove "if is even, then is even" directly. You would start with and get stuck: tells you nothing useful. But an implication and its contrapositive are equivalent, and the contrapositive, "if is odd, then is odd", is easy to prove.
Worked example
If is even, then is even
Prove that for all , if is even then is even.
Step 1: Choose the contrapositive
A direct proof stalls: from there is no useful way to get at . Instead prove the contrapositive: "if is odd, then is odd".
An implication and its contrapositive are logically equivalent, so proving one proves the other.
Step 2: Assume n is odd
Let , where .
Step 3: Square it
Step 4: Conclude
Since , is odd. This proves the contrapositive, so the original statement is true: if is even, then is even.
Try it yourself first, then check the working one step at a time.
Answer
The contrapositive, "if is odd then is odd", is true because . Hence if is even, is even.
Method
Write the contrapositive and say you are proving it.
Prove it directly.
Bring the conclusion back to the original statement.
Watch out for
Proving "if is even then is even", which is the converse.
Common mistake
Don't prove the converse by accident
To prove "if is even then is even", showing that "if is even then is even" proves the converse, a different statement. The contrapositive negates and swaps: start from " is odd" and finish at " is odd".
To prove "for , if is even then is odd" using the contrapositive, which statement should you prove?
Exam tip
Name the method
Start a contrapositive proof by saying so: "We prove the contrapositive: if is odd then is odd." Start a proof by cases by listing the cases and why they cover everything: "Every integer is even or odd." Finish by bringing the cases or the contrapositive back to the original statement.
Summary
Proof by cases: split into cases that cover every possibility (even/odd, or , , ) and prove each one.
is even for every integer , because is always even.
A perfect square leaves remainder 0 or 1 on division by 3.
To prove , you may prove the equivalent contrapositive instead.
"If is even then is even" is proved through its contrapositive, and it is the key step in proving is irrational.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.