Proof by Contradiction and Contrapositive

Proof by Contrapositive

Sometimes a direct proof is awkward, so we use indirect techniques. Proof by contrapositive proves if $p$ then $q$ by proving the equivalent statement if $\neg q$ then $\neg p$.

Use this when negating the conclusion gives a better starting point.

Example: To prove "if $n^2$ is even, then $n$ is even," prove the contrapositive: "if $n$ is odd, then $n^2$ is odd."

Proof by Contradiction

Proof by contradiction (reductio ad absurdum) assumes the target statement is false, then derives a logical contradiction (like $0 = 1$). Valid steps cannot lead to a contradiction, so the original statement must be true.

Example ($\sqrt{2}$ is irrational): Assume $\sqrt{2} = a/b$ in lowest terms. Squaring gives $a^2 = 2b^2$, forcing $a$ and $b$ both even, which contradicts lowest terms.

Pitfall: Don't confuse them. Contrapositive proves an equivalent conditional directly. Contradiction assumes the whole statement false to hunt for an impossibility.