Proof by Contrapositive | Real Analysis

The

n = 1..12

grid where the

n^2

-even rows are exactly the

n

-even rows — where the direct proof of "

n^2

even

\Rightarrow

n

even" stalls, the contrapositive "odd

n

\Rightarrow

odd

n^2

" opens up through

(2k+1)^2 = 2(2k^2+2k)+1

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.