Discrete Math · Undergraduate

Proof Techniques: Direct, Contrapositive and Contradiction

Quick answer

A proof is a chain of steps, each justified, from what is known to what is claimed. A direct proof of "if p, then q" assumes p and works forward to q, usually by unpacking definitions. Proving the contrapositive, "if not q, then not p", is equivalent and sometimes simpler. A proof by contradiction assumes the statement is false and derives something impossible. These three methods prove that the sum of two odd numbers is even, that √2 is irrational, and that there are infinitely many primes.

What you'll learn

  • Write a direct proof by unpacking definitions
  • Prove a conditional through its contrapositive
  • Write a proof by contradiction
  • Disprove a general claim with a counterexample

What counts as a proof

A proof shows that a statement is true in every case, by a chain of steps each of which follows from definitions, earlier results or plain algebra. Checking examples is not enough: n2+n+41n^2 + n + 41 is prime for n=0,1,…,39n = 0, 1, \ldots, 39, but not for n=40n = 40, where it equals 41241^2. A proof covers every case at once.

Most statements have the form “if pp, then qq”. Three methods handle them.

Direct proof

Assume pp. Unpack the definitions, and work forward until qq appears.

Proof by contrapositive

The contrapositive of p→qp \to q is ¬q→¬p\neg q \to \neg p, and the two are equivalent. Sometimes ¬q\neg q is the better starting point.

Why contradiction works

A statement is either true or false. If assuming it is false leads to an impossibility, such as a number that is both even and odd, then “false” was not an option. So it must be true. Contradiction is most useful for statements of the form “there is no…” or “this is not…”, where a direct approach has nothing to build on.

Counterexamples

To show “for all…” is false, one counterexample is enough. “Every prime is odd” is false because 22 is prime and even.

Common mistakes

Practice problems

  1. Prove that the sum of two even numbers is even.

    Answer

    2a+2b=2(a+b)2a + 2b = 2(a + b), which is even.

    Full solution

    Write the numbers as 2a2a and 2b2b for integers aa and bb; their sum is 22 times the integer a+ba + b.

  2. Prove that the product of two odd numbers is odd.

    Answer

    (2a+1)(2b+1)=2(2ab+a+b)+1(2a + 1)(2b + 1) = 2(2ab + a + b) + 1.

    Full solution

    Expand: 4ab+2a+2b+14ab + 2a + 2b + 1, which is 22 times an integer plus 11.

  3. Write the contrapositive of “if n2n^2 is odd, then nn is odd”, and prove it.

    Answer

    “If nn is even, then n2n^2 is even”: (2k)2=2(2k2)(2k)^2 = 2(2k^2).

    Full solution

    Negate both parts and swap them. An even nn is 2k2k, and its square is twice an integer.

  4. Find a counterexample to ”n2+n+41n^2 + n + 41 is prime for every whole number nn”.

    Answer

    n=40n = 40 gives 1,681=4121{,}681 = 41^2.

    Full solution

    402+40+41=41(40+1)40^2 + 40 + 41 = 41(40 + 1). (n=41n = 41 also works: 41(41+1+1)41(41 + 1 + 1).)

  5. Find a counterexample to “if a2=b2a^2 = b^2, then a=ba = b”.

    Answer

    a=2a = 2, b=−2b = -2

    Full solution

    Both squares are 44, but 2≠−22 \ne -2.

  6. Which method would you use to prove “there is no largest even number”? Sketch the proof.

    Answer

    Contradiction: if NN were the largest even number, N+2N + 2 would be even and larger.

    Full solution

    Assuming a largest one exists gives a concrete NN to work with, and N+2N + 2 breaks the assumption.

  7. In Example 4, is N=p1p2⋯pk+1N = p_1p_2\cdots p_k + 1 always prime? Try the primes 2,3,5,7,11,132, 3, 5, 7, 11, 13.

    Answer

    No: 30,031=59×50930{,}031 = 59 \times 509.

    Full solution

    The proof only needs NN to have a prime factor outside the list. Here the new primes 5959 and 509509 appear.

  8. A student proves “if nn is even, then n2n^2 is even” and claims to have shown “if n2n^2 is even, then nn is even”. What is wrong?

    Answer

    That proves the converse, a different statement.

    Full solution

    The statement needs its own proof, such as the contrapositive argument of Example 2.

Frequently asked questions

What is a direct proof?

A proof of "if p, then q" that assumes p and reasons step by step to q, typically by writing out the definitions involved.

When should you prove the contrapositive instead?

When the conclusion's negation gives you something concrete to work with. To show "if n² is even then n is even", it is easier to assume n is odd and show n² is odd.

What is a proof by contradiction?

Assume the statement is false, then reason to something impossible, such as a number that is both even and odd. The assumption must have been wrong, so the statement is true.

How do you disprove a statement?

For a claim about all cases, one counterexample is enough. The claim "every prime is odd" falls to the single example 2.

Do examples prove a general statement?

No. Checking cases can suggest a pattern but cannot prove it holds for every case; a proof must cover all of them at once.

What to learn next