A direct proof starts from the hypothesis and reaches the conclusion through known facts. A proof by contrapositive proves ∼q⇒∼p instead of p⇒q
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
write a direct proof with clear steps;
prove a statement through its contrapositive;
prove a statement about finitely many cases by exhaustion;
disprove a statement with a counterexample.
The direct proof
A direct proof of "if p then q" starts by assuming p. Each line follows from the one before, from a definition or from a known fact. The last line is q.
Claim. The sum of two odd integers is even.
Proof.
Let the odd integers be 2m+1 and 2n+1, where m and n are integers.
Their sum is 2m+2n+2=2(m+n+1).
m+n+1 is an integer, so the sum is twice an integer.
So the sum is even. This completes the proof.
A second example. If n is odd, then n2−1 is divisible by 8.
Write n=2k+1. Then n2−1=4k2+4k=4k(k+1).
One of k and k+1 is even, so k(k+1) is even.
So 4k(k+1) is 4 times an even number, a multiple of 8.
Check with n=7: 49−1=48=8×6.
The proof by contrapositive
Sometimes the hypothesis gives little to work with. Then prove the contrapositive, which is equivalent.
Claim. For an integer n, if n2 is even, then n is even.
A direct start, "n2=2k", does not lead anywhere easily. So prove the contrapositive: if n is odd, then n2 is odd.
Let n=2k+1.
Then n2=4k2+4k+1=2(2k2+2k)+1, which is odd.
The contrapositive is true, so the claim is true.
Another one. If a+b≥20 for real numbers a and b, then a≥10 or b≥10. The contrapositive is: if a<10 and b<10, then a+b<20. That is clear, because adding the two inequalities gives it.
Proof by exhaustion
When there are only a few cases, check them all. This is a proof by exhaustion.
Claim. No perfect square ends in the digit 2, 3, 7 or 8.
The last digit of n2 depends only on the last digit of n. Check the ten digits:
0→0, 1→1, 2→4, 3→9, 4→6;
5→5, 6→6, 7→9, 8→4, 9→1.
The last digits of squares are 0,1,4,5,6,9. None is 2, 3, 7 or 8.
Disproof by counterexample
To show that a for-all claim is false, one counterexample is enough.
"n2+n+41 is prime for every whole number n." It is prime for n=0,1,…,39. But at n=40 it is 1681=412.
"Every number 22n+1 is prime." This was believed for n=0 to 4. But 232+1=641×6700417.
"If a2=b2, then a=b." The pair a=3, b=−3 is a counterexample.
Forty cases that work do not prove a claim. One case that fails disproves it.
A note for other syllabi
A-Level Mathematics names these methods proof by deduction, proof by exhaustion and disproof by counterexample. IB Analysis and Approaches asks for simple deductive proofs, often from the left side to the right side of an identity. The methods are the same.
Practise with new numbers
Try it in Python
The program searches for counterexamples. It tests Euler's formula n2+n+41, then checks the factor 641 of 232+1.
Common mistakes
Proving by examples. Checking ten cases is not a proof of a statement about every integer, unless there are only ten cases.
Assuming the conclusion. A direct proof starts from the hypothesis, never from what you want.
Proving the converse instead. "If n is even, then n2 is even" is the converse of the claim above, not its contrapositive.
Using the same letter for two numbers. Two odd integers are 2m+1 and 2n+1, not 2k+1 twice.
Remember these
Direct: assume p, reach q.
Contrapositive: assume ∼q, reach ∼p.
Exhaustion: check every one of finitely many cases.
One counterexample disproves a for-all claim.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Prove that the product of an even integer and any integer is even.
Give a counterexample to "every odd number greater than 1 is prime".
To prove "if 3n+2 is odd, then n is odd" by contrapositive, what do you assume?
What are the possible last digits of a fourth power n4?
Disprove: "For every real x, x2=x."
References
NCERT, Mathematics Textbook for Class XII, Part II, Appendix 1, Proofs in Mathematics.
Richard Hammack, Book of Proof, third edition, Chapters 4 and 5 (direct and contrapositive proof).
Enroll free in Valid Arguments and Methods of Proof
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.