Introduction to Proofs · Direct proof and counterexamples
Read a quantified implication, prove it from definitions, and refute a false statement with a counterexample. You only need basic integer algebra.
Lesson and summary
To prove that P implies Q for every integer, choose an arbitrary integer satisfying P and derive Q. An even integer can be written as 2k for some integer k. An odd integer can be written as 2k + 1. A single input with P true and Q false refutes a universal implication.
- Assume both integers are odd
- a = 2m + 1, b = 2n + 1
- a + b = 2(m + n + 1)
- The sum is even
Worked example
If a and b are odd, write a = 2m + 1 and b = 2n + 1 for integers m and n. Then a + b = 2(m + n + 1), which is even because m + n + 1 is an integer. The converse is false: a = b = 2 gives an even sum although neither input is odd.
Common mistake
Checking many examples cannot establish a universal claim. To refute one, choose an example that satisfies every assumption and violates the conclusion.
Practice
Prove that the product of two odd integers is odd. Then test the statement that every integer with an even sum with 4 is odd.
Practice solution
Expand (2m + 1)(2n + 1) = 2(2mn + m + n) + 1. The expression in parentheses is an integer. For the second claim, 2 + 4 is even and 2 is even, so 2 is a counterexample.
Mini-exam · 10 points
Prove that if an integer is divisible by 6 then it is divisible by 3 (6 points). State and refute the converse (4 points).
Exam answer key
Write n = 6k = 3(2k) for an integer k. Since 2k is an integer, 3 divides n. The converse says that divisibility by 3 implies divisibility by 6. The integer 9 refutes it.
MIT OCW · Mathematics for Computer Science
Next lesson: Mathematical induction
Virtual lab · Find a counterexample
Distinguish evidence from proof and construct a counterexample to a converse.
Free tool built into this page. Use it in your browser without an account or download.
Procedure
Test a = 3 and b = 5, then a = 2 and b = 4. The checker reports whether both inputs are odd and whether the sum is even. Find inputs that refute “if the sum is even, both inputs are odd.” Then prove the original implication using algebra.
Expected results and answer check
2 + 4 = 6 is even although both inputs are even, which refutes the converse. For odd inputs, write a = 2m + 1 and b = 2n + 1. Their sum is 2(m + n + 1), which is even for all integers m and n.
The checker tests examples. The algebra establishes the claim for every integer.