Method

Proof by Contrapositive

A proof by contrapositive is a method used to prove a conditional statement by proving its contrapositive. This method is based on the fact that a conditional statement is equivalent to its contrapositive.

rc Statement:& P ⇒ Q &⇕ Contrapositive:& ¬ Q ⇒ ¬ P

For example, consider the following statement.

For any integer n, if n^2 is odd, then n is odd.

There are two main steps to follow to prove this statement by contrapositive.

Form the Contrapositive Statement

In order to form the contrapositive of the statement, first determine the hypothesis P and conclusion Q in the statement. If n^2is odd_P, thenn is odd_Q. The contrapositive is formed by negating both P and Q and writing the converse.

¬ P	¬ Q	Contrapositive (¬ Q ⇒ ¬ P)
n^2 is not odd	n is not odd	If n is not odd, then n^2 is not odd.

Prove the Contrapositive Statement Directly

Assume that n is not an odd integer. It implies that n is even, which means that n=2k for some integer k. In order to show that n^2 is not odd, square both sides of the equation n=2k.

n=2k

RaiseEqn

LHS^2=RHS^2

n^2=(2k)^2

PowProdII

(a b)^m=a^m b^m

n^2=2^2 k^2

CalcPow

Calculate power

n^2=4k^2

FactorOut

Factor out 2

n^2=2(2k^2)

From the latter expression, we conclude that n^2 is even. It means that n^2 is not odd. Therefore, we proved that if n is not odd, then n^2 is not odd.

Recommended exercises