Proof by the Contrapositive

Where a direct proof stalls

The claim: for every whole number n, if $n^2$n² is even, then n is even.

A direct proof starts from the hypothesis. $n^2$n² even means $n^2=2m$n² = 2m for some whole number m, and the proof would have to turn that into n = 2k. Nothing does. Taking the square root gives $n=\sqrt{2m}$n = √(2m), which says nothing about whether n is even. The hypothesis is about $n^2$n² and the conclusion is about n, and going from a square back to the number is the hard direction.

Prove the contrapositive instead

The contrapositive of “if P, then Q” is “if not Q, then not P”: swap the two parts and negate each one. A statement and its contrapositive are true in exactly the same cases. Each is broken only by a case where P holds and Q fails, so a case that breaks one breaks the other, and a proof of either one is a proof of both.

Here P is “$n^2$n² is even” and Q is “n is even”. For a whole number, not even means odd, so the contrapositive is: if n is odd, then $n^2$n² is odd. Its hypothesis is about n, and that is the easy direction: squaring a number of known form is algebra.

Two other rearrangements are not equivalent to the claim. The converse, if n is even then $n^2$n² is even, swaps the parts without negating them. The inverse, if $n^2$n² is odd then n is odd, negates the parts without swapping them. Both happen to be true, but proving either one does not prove the claim.

The proof

Suppose n is odd. By the definition of odd, n = 2k + 1 for some whole number k.

Square it: $n^2={\left(2k+1\right)}^2=4k^2+4k+1$n² = (2k + 1)² = 4k² + 4k + 1. Take 2 out of the first two terms: $n^2=2\left(2k^2+2k\right)+1$n² = 2(2k² + 2k) + 1.

Since k is a whole number, $2k^2+2k$2k² + 2k is a whole number too. So $n^2$n² is 2 times a whole number, plus 1, and by the definition of odd, $n^2$n² is odd.

One case as a check on the algebra: k = 3 gives n = 7, and 2(2 × 9 + 2 × 3) + 1 = 2 × 24 + 1 = 49, which is $7^2$7². The check is not part of the proof.

A square of side 2k + 1, cut at 2k along each side. The pieces are a square $4k^2$4k², two strips of 2k and one unit square. The first three are each 2 times a whole number, so the single unit square left over is what makes the square of an odd number odd.

Nothing is left to do

The contrapositive is proved: every odd n has an odd square. So no odd n has an even square, and if $n^2$n² is even, n cannot be odd. That is the claim. There is no final step turning one statement into the other, because they are the same statement in two forms.

Checking examples afterwards adds nothing. The table below agrees with the claim in eight rows, but eight rows are eight cases, and the proof above covers every whole number.

n from 1 to 8 and their squares. In every row, n and $n^2$n² are both even or both odd.

When to choose it

Choose the contrapositive when the hypothesis gives little to write down and the negated conclusion gives a lot. “n is odd” becomes n = 2k + 1, an expression to compute with; “$n^2$n² is even” becomes only $n^2=2m$n² = 2m.

Another claim of this kind: if x + y is odd, then x and y have different parity, one even and one odd. Its contrapositive is: if x and y have the same parity, then x + y is even. Same parity means two cases. Both even: x = 2a and y = 2b, so x + y = 2(a + b), which is even. Both odd: x = 2a + 1 and y = 2b + 1, so x + y = 2a + 2b + 2 = 2(a + b + 1), which is even. In both cases x + y is even, so the contrapositive is proved, and with it the claim.

Not every claim needs it. “The sum of two odd numbers is even” is proved directly in three lines, and turning it round gains nothing. “There is a prime above 100” has no if-part at all, so it has no contrapositive to take.

The usual mistakes

Proving the converse. “If n is even, then $n^2$n² is even” is true, but it is a different claim, and proving it says nothing about the original.

Doing only one of the two moves. Swapping without negating gives the converse, and negating without swapping gives the inverse; the contrapositive swaps the parts and negates each.

Adding a step at the end. Once “if not Q, then not P” is proved, “if P, then Q” is proved, and nothing remains: no converse, no examples.

Invoices under a signing limit

In the application below, an auditor’s claim, that a purchase of $10000 or more split into two invoices has an invoice of $5000 or more, is proved through its contrapositive: two invoices under $5000 add to less than $10000. The same argument then finds how many invoices a purchase must be split into to slip under a review limit.