Introduction to proof methods: direct, contrapositive, contradiction

The proof questions are the most feared part of the discrete math midterm. In fact most of them are template questions: “Give a direct proof”, “Prove by contraposition”, “Prove by contradiction”. On this page you will learn the English skeleton of each method. Half of any proof is writing the definition correctly. A proof that starts without the definition usually falls apart.

Golden rules:

1. Start with the definition. The moment you write ”$n$ is odd”, immediately write “so $n = 2k + 1$ for some integer $k$”.
2. A new letter for every new number. If $m$ and $n$ are odd, $m = 2a + 1$, $n = 2b + 1$.
3. Finish with the definition of your goal. ”$= 2m + 1$, where $m = \dots$ is an integer. Therefore … is odd.”
4. An example is not a proof, but a single counterexample refutes a $\forall$ claim.
5. If the hypothesis is not useful, switch to the contrapositive.

Terms and definitions

• Theorem: an important claim that has been proved true. Lemma: a helper claim used in a bigger proof. Corollary: a result that follows immediately from a theorem. Conjecture: a claim believed to be true but not proved. Axiom: a starting truth accepted without proof.
• Most theorems start with “for all” but do not write it: “If $n$ is odd, then $n^2$ is odd” really means $\forall n\,(P(n) \to Q(n))$. In the proof you take an arbitrary $n$, and at the end universal generalization makes it hold for all $n$.

Definitions to memorize:

Direct proof

To prove $p \to q$, assume $p$ and reach $q$ using definitions and algebra.

Theorem. If $m$ is even and $n$ is odd, then $m + n$ is odd.

Proof. Let m be even and n be odd.            state the hypothesis
Then m = 2a and n = 2b + 1 for some            definitions, TWO different letters
integers a and b.
So m + n = 2a + 2b + 1 = 2(a + b) + 1.         algebra, factor out the 2
Since a + b is an integer, m + n is odd        definition of the goal
by definition.  ∎

PITFALL · Giving the same letter to two numbers. If you write $m = 2k$, $n = 2k + 1$, you have said $n = m + 1$; the proof then works only for consecutive numbers. Every number gets its own letter.

Proof by contraposition

Since $p \to q \equiv \lnot q \to \lnot p$, it is enough to prove the contrapositive. When? When the hypothesis does not give you a useful equation: ”$3n + 7$ is even”, ”$n^2$ is odd”, ”$xy$ is irrational”.

Theorem. If $n$ is an integer and $3n + 7$ is even, then $n$ is odd.

If you try it directly: $3n + 7 = 2k \Rightarrow n = \tfrac{2k - 7}{3}$. This does not help; you cannot see that $n$ is odd.

Proof. We prove the contrapositive:
"If n is even, then 3n + 7 is odd."
Let n be even, so n = 2k for some integer k.
Then 3n + 7 = 6k + 7 = 6k + 6 + 1 = 2(3k + 3) + 1.
Since 3k + 3 is an integer, 3n + 7 is odd.
Since the contrapositive is true, the original statement is true.  ∎

Writing the contrapositive explicitly as a sentence earns marks. Watch De Morgan when the conclusion contains “and/or”: the negation of ”$x \ge 1$ or $y \ge 1$” is ”$x < 1$ and $y < 1$”.

Proof by contradiction

Assume the claim is false and reach an absurdity ($r \land \lnot r$). For $p \to q$ the assumption is ”$p$ is true and $q$ is false”. When? For negative claims such as “irrational”, “there is no …”, “infinitely many”.

Theorem. $\sqrt{2}$ is irrational.

Proof. Assume, for contradiction, that √2 is rational.
Then √2 = a/b where a, b are integers, b ≠ 0, and the
fraction is in lowest terms (a and b have no common factor > 1).
Squaring: 2 = a²/b², so a² = 2b². Hence a² is even,
so a is even (if a were odd, a² would be odd).
Write a = 2c. Then 4c² = 2b², so b² = 2c², and b² is even,
so b is even.
Now a and b are both even, so 2 is a common factor.
This contradicts "lowest terms". Hence √2 is irrational.  ∎

Here the lemma “a² even ⇒ a even” was used; you proved it by contraposition (question 1). Big proofs are built from small lemmas.

TIP · Name the contradiction. On the last line write what contradicts what: “This contradicts the assumption that $a/b$ is in lowest terms.” The word “contradiction” alone is weak.

Proof by cases

If the hypothesis splits into several cases, prove each case separately. The cases must cover all possibilities (exhaustive).

Theorem. For every integer $n$, $n^2 + n$ is even.

Proof. Case 1: n is even, n = 2k.
  n² + n = 4k² + 2k = 2(2k² + k), even.
Case 2: n is odd, n = 2k + 1.
  n² + n = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1), even.
Every integer is even or odd, so n² + n is even for all n.  ∎

A shorter way: $n^2 + n = n(n+1)$ is the product of two consecutive numbers and one of them is always even. But you have to justify this sentence too; on the exam the two-case proof is safer.

Existence proofs and counterexamples

Existence proof (constructive): to say “There exists $x$ with $P(x)$”, show a concrete $x$. Example: “There is a positive integer that can be written as the sum of two cubes in two different ways.” $1729 = 1^3 + 12^3 = 9^3 + 10^3$. Done.

Nonconstructive: proving that something exists without exhibiting it (for example, showing that one of two cases works without saying which). This comes up less in this course.

Counterexample: to show that $\forall x\, P(x)$ is false, a single $c$ for which $P(c)$ is false is enough. The danger is the reverse: however many examples you try, a $\forall$ claim is not proved by examples. $n^2 - n + 11$ is prime for the first ten values and collapses at $n = 11$.

Other small templates

• Vacuous proof: if $p$ can never be true, $p \to q$ is automatically true. “If $n$ is an integer with $n^2 < 0$, then $n = 7$.” The hypothesis is never satisfied.
• Trivial proof: if $q$ is always true, $p \to q$ is true.
• iff proof: $p \leftrightarrow q \equiv (p \to q) \land (q \to p)$. Write the two directions under separate headings: ”(⇒)” and ”(⇐)”. You may use the contrapositive for the second direction.

Which method should I choose?

Common mistakes