Proof by Contrapositive | Real Analysis

Lay out an even-odd table and set a statement beside its contrapositive. This is the detour for when the direct road is blocked.

Some statements resist a frontal attack. Then flip and negate: prove the contrapositive instead. It always shares the original's truth value. Settle one side and the other comes free.

For example, if a square is even, the number itself is even. Instead of studying squares, look only at odd numbers. Squaring an odd number always gives an odd number. So an even square never came from an odd number.

Examples & Exercises

Prove completely, by contrapositive, that for an integer $n$ , "if $n^2$ is even then $n$ is even".

Reduce the claim to its contrapositive, "if $n$ is odd then $n^2$ is odd", and prove that by the odd-square expansion.

n^2 \text{ even} \Rightarrow n \text{ even} \quad\Longleftrightarrow\quad n \text{ odd} \Rightarrow n^2 \text{ odd}

n = 7

(odd):

n = 2 \cdot 3 + 1

n^2 = 49 = 2 \cdot 24 + 1

— odd. The contrapositive computation is on display.

Show proof

The claim is $P \Rightarrow Q$ with $P$ : " $n^2$ is even" and $Q$ : " $n$ is even". An implication is logically equivalent to its contrapositive (both fail exactly when $P$ is true and $Q$ false), so we prove $\lnot Q \Rightarrow \lnot P$ : "if $n$ is odd then $n^2$ is odd".
The contrapositive is proved directly: if $n$ is odd, then $n = 2k + 1$ for some integer $k$ , and $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ .
Since $2k^2 + 2k$ is an integer, $n^2$ is odd.
Check in the scene: $n = 7$ gives $k = 3$ and $n^2 = 49 = 2 \cdot (2 \cdot 9 + 6) + 1 = 2 \cdot 24 + 1$ .
The contrapositive is proved, so by equivalence the original claim "if $n^2$ is even then $n$ is even" is proved.
(Why the direct attempt stalls: the assumption $n^2 = 2m$ gives no handle for computing with $n$ — the contrapositive swaps it for the workable form $n = 2k + 1$ .)
$(2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Prove by contrapositive that for an integer $n$ , "if $3n + 2$ is odd then $n$ is odd".

First explain why the direct route is awkward: " $3n + 2$ odd" only yields " $3n$ odd", with no direct grip on $n$ itself.

3n + 2 \text{ odd} \Rightarrow n \text{ odd} \quad\Longleftrightarrow\quad n \text{ even} \Rightarrow 3n + 2 \text{ even}

n = 8

(even):

n = 2 \cdot 4

3n + 2 = 26 = 2(3 \cdot 4 + 1) = 2 \cdot 13

— even. The contrapositive direction is on display.

Show proof

Why the direct route is awkward: assuming $3n + 2$ is odd gives $3n = (3n + 2) - 2$ , so $3n$ is odd.
But passing from "3 times $n$ is odd" to " $n$ is odd" needs a separate argument that $n$ cannot be even — there is no computable form of $n$ to work with.
So we turn to the contrapositive: "if $n$ is even then $3n + 2$ is even".
Prove the contrapositive directly: if $n$ is even, write $n = 2k$ with $k$ an integer; then $3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$ .
Since $3k + 1$ is an integer, $3n + 2$ is even.
The contrapositive is proved, so by equivalence the original claim "if $3n + 2$ is odd then $n$ is odd" is proved.
Check in the scene: $n = 8 = 2 \cdot 4$ gives $3n + 2 = 26 = 2(3 \cdot 4 + 1) = 2 \cdot 13$ , even.

Prove that for an integer $n$ , "if $n^2$ is divisible by 3 then $n$ is divisible by 3".

Take the contrapositive, then split the case "3 does not divide $n$ " into $n = 3k + 1$ and $n = 3k + 2$ , showing in each case that 3 does not divide $n^2$ .

n = 3k+1 \Rightarrow n^2 = 3(3k^2 + 2k) + 1, \qquad n = 3k+2 \Rightarrow n^2 = 3(3k^2 + 4k + 1) + 1

n = 9

n^2 = 81 = 3 \cdot 27

— divisible by 3, and

n = 9 = 3 \cdot 3

is too. A check in the statement's own form.

Show proof

We prove the contrapositive: "if 3 does not divide $n$ then 3 does not divide $n^2$ ".
By the division algorithm, if 3 does not divide $n$ the remainder is 1 or 2, so $n = 3k + 1$ or $n = 3k + 2$ for some integer $k$ .
Compute each case.
Case 1: if $n = 3k + 1$ then $n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$ — remainder 1 on division by 3, so 3 does not divide $n^2$ .
Case 2: if $n = 3k + 2$ then $n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$ — again remainder 1, so 3 does not divide $n^2$ .
Both cases give the contrapositive's conclusion, so the contrapositive is proved, and by equivalence so is the original claim.
Check in the scene: $n = 9 = 3 \cdot 3$ is divisible by 3 and $n^2 = 81 = 3 \cdot 27$ is too.