Proof by contrapositive

From AoPSWiki

Proof by contrapositive is a method of proof in which the contrapositive of the desired statement is proven, and thus it follows that the original statement is true. Generally, this form is only used when it is impossible to prove the original statement directly.

Problems

Introductory

• Show that if and are two integers for which is even, then and have the same parity.

Solution

The contrapositive of this is

If and are two integers with opposite parity, then their sum must be odd.

So we assume and have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose is even and is odd. Thus, there are integers and for which and . Now then, we compute the sum , which is an odd integer by definition.

• Show that if is an odd integer, then is odd.

Solution

Suppose is an even integer. Then there exists an integer such that . Thus . Since is an integer, is even. Therefore is not odd.

Intermediate

Olympiad