What Is Proof by Contradiction?

Proof by contradiction is a method of proving a statement by assuming its negation and then showing that this leads to a contradiction.

Example: Prove that if $n^2$ is odd, then $n$ is odd.

Proof (by contradiction)
Assume $n^2$ is odd but $n$ is not odd. The truth or falsity of this assumption will determine the truth of the original.

• If $n$ is not odd, then $n$ must be even, so let $n = 2k$ for some integer $k$.
• $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$.
• Hence $n^2$ is even.

Thus, when $n$ is even, $n^2$ is also even. This contradicts the assumption that $n^2$ is odd.
Therefore, the assumption is false, and the original statement is true:
If $n^2$ is odd, then $n$ is odd. □