Proof Techniques: Direct, Contradiction and Contrapositive

For many students, the jump from school maths to university maths is really a jump from calculating answers to proving statements. The good news is that most proofs you meet early on follow a handful of patterns. Learn the three most important ones, direct proof, contradiction and contrapositive, and you will know how to start almost any first-year proof.

What a Proof Actually Is

A proof is a chain of logical steps that starts from things you accept (definitions, axioms, earlier theorems) and ends with the statement you want. Each step must follow from the earlier ones. Examples do not count as proof: checking that a statement holds for 10 cases tells you nothing about the 11th.

Most statements you prove have the form "if \( P \), then \( Q \)", written \( P \Rightarrow Q \). The three techniques below are three different ways of attacking that shape.

Definitions You Will Need

• An integer \( n \) is even if \( n = 2k \) for some integer \( k \).
• An integer \( n \) is odd if \( n = 2k + 1 \) for some integer \( k \).
• A real number is rational if it equals \( \frac{a}{b} \) with integers \( a, b \) and \( b \neq 0 \).

Writing definitions as equations is half the battle. It turns a sentence into something you can do algebra with.

Technique 1: Direct Proof

Template: Assume \( P \) is true. Use definitions and known results to reach \( Q \).

Worked Example 1: The Sum of Two Odd Integers Is Even

Claim: If \( m \) and \( n \) are odd, then \( m + n \) is even.

Proof.

1. Assume \( m \) and \( n \) are odd.
2. By definition, \( m = 2a + 1 \) and \( n = 2b + 1 \) for some integers \( a, b \). Use different letters, because \( m \) and \( n \) need not be equal.
3. Add them:

$$ m + n = (2a + 1) + (2b + 1) = 2a + 2b + 2 = 2(a + b + 1). $$

4. Since \( a + b + 1 \) is an integer, \( m + n \) is of the form \( 2k \), so it is even. \( \blacksquare \)

Direct proof works best when the hypothesis gives you something concrete to compute with.

Technique 2: Proof by Contrapositive

The statement \( P \Rightarrow Q \) is logically equivalent to its contrapositive, \( \text{not } Q \Rightarrow \text{not } P \). Proving one proves the other.

Template: Assume \( Q \) is false. Show that \( P \) must then be false.

Be careful not to confuse the contrapositive with the converse \( Q \Rightarrow P \), which is a different statement and may be false.

Worked Example 2: If \( n^2 \) Is Even, Then \( n \) Is Even

A direct attack is awkward: knowing \( n^2 = 2k \) does not easily tell you about \( n \). The contrapositive is much cleaner.

Contrapositive: If \( n \) is odd, then \( n^2 \) is odd.

Proof.

1. Assume \( n \) is odd, so \( n = 2k + 1 \) for some integer \( k \).
2. Square it:

$$ n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. $$

3. Since \( 2k^2 + 2k \) is an integer, \( n^2 \) is odd.
4. We have proved the contrapositive, so the original statement is true. \( \blacksquare \)

When to use it: whenever "not \( Q \)" gives you an equation to work with but \( P \) does not.

Technique 3: Proof by Contradiction

Template: Assume the statement is false. Follow the logic until you reach something impossible, such as \( 1 = 0 \) or "this fraction is both in lowest terms and not in lowest terms". Since a true assumption cannot lead to a false conclusion, the assumption must be wrong.

Worked Example 3: \( \sqrt{2} \) Is Irrational

Proof.

1. Suppose, for contradiction, that \( \sqrt{2} \) is rational.
2. Then \( \sqrt{2} = \frac{a}{b} \) with integers \( a, b \), \( b \neq 0 \), and we may assume the fraction is in lowest terms (so \( a \) and \( b \) share no common factor other than 1).
3. Square both sides and rearrange:

$$ 2 = \frac{a^2}{b^2} \quad \Longrightarrow \quad a^2 = 2b^2. $$

4. So \( a^2 \) is even. By Worked Example 2, \( a \) is even, so \( a = 2c \) for some integer \( c \).
5. Substitute:

$$ (2c)^2 = 2b^2 \quad \Longrightarrow \quad 4c^2 = 2b^2 \quad \Longrightarrow \quad b^2 = 2c^2. $$

6. So \( b^2 \) is even, and hence \( b \) is even.
7. Now both \( a \) and \( b \) are even, so they share the factor 2. This contradicts step 2.
8. Therefore \( \sqrt{2} \) is irrational. \( \blacksquare \)

Notice how step 4 reused an earlier result. Building proofs from smaller proved facts is exactly how mathematics grows.

Another Classic: There Are Infinitely Many Primes

Suppose there are only finitely many primes, \( p_1, p_2, \ldots, p_k \). Let

$$ N = p_1 p_2 \cdots p_k + 1. $$

Dividing \( N \) by any \( p_i \) leaves remainder 1, so no \( p_i \) divides \( N \). But \( N > 1 \), so it has at least one prime factor, which must be a prime not on our list. That contradicts the assumption that the list was complete. \( \blacksquare \)

How to Choose a Technique

Ask yourself these questions in order:

1. Does the hypothesis give me an equation? Try a direct proof first.
2. Is the conclusion a "negative" statement? Phrases like "is irrational", "has no solution" or "there is no largest" often call for contradiction.
3. Is the negation of the conclusion easier to work with than the hypothesis? Use the contrapositive.

If you are stuck, write down the contrapositive and the negation side by side. One of them usually looks more promising.

Writing Proofs Clearly

• Announce your method: "We prove the contrapositive" or "Suppose, for contradiction, that…".
• Introduce every variable: "for some integer \( k \)" is not optional.
• One idea per line. Short steps are easier to check and harder to get wrong.
• State where you used each assumption. If a hypothesis is never used, either the proof is wrong or the hypothesis is unnecessary.
• Finish with a clear conclusion, then a symbol such as \( \blacksquare \) or "as required".

Common Mistakes

• Proving the converse instead of the original statement.
• Using the same letter for two different integers, e.g. writing both \( m \) and \( n \) as \( 2k + 1 \).
• Starting from the conclusion and working backwards without making sure every step is reversible.
• Calling a few examples a proof.

Key Takeaways

• A direct proof assumes \( P \) and builds a chain of steps to \( Q \).
• The contrapositive \( \text{not } Q \Rightarrow \text{not } P \) is equivalent to the original statement and is often easier.
• Proof by contradiction assumes the statement is false and derives something impossible.
• Translate every definition into an equation before you start manipulating.
• Clear structure, introduced variables and a stated conclusion make proofs easy to mark.

If your discrete maths or analysis assignment is full of proofs you cannot crack, Amathify's PhD scholars can walk you through each one step by step. Reach us on WhatsApp or send your question through the "Ask a Question" form.