Proof Methods Reference

Methods of Proof

A proof explains why a mathematical claim must be true; the statement’s form often suggests a useful method.

Solved Examples

Jump directly to a worked example by type.

Fact Table

IdeaMeaningUse or Check
Direct proof Start from the hypothesis and use definitions or known facts to reach the conclusion. Useful for $p\to q$.
Contrapositive Prove $\neg q\to\neg p$ instead of $p\to q$. A statement and its contrapositive are equivalent.
Contradiction Assume the claim is false and derive an impossibility. State clearly which assumption leads to the contradiction.
Counterexample One valid input that violates a universal claim. One counterexample disproves “for every.”

Content Formulas

Conditional Equivalence
$$p\to q\equiv\neg q\to\neg p$$
Even Integer
$$n=2k\quad\text{for some }k\in\mathbb Z$$
Odd Integer
$$n=2k+1\quad\text{for some }k\in\mathbb Z$$
A proof must use the definitions in the correct direction. A few confirming examples can suggest a theorem, but they do not prove a statement for every integer.

Classic Examples

Direct Proof: An Even Square

Prove that if $n$ is even, then $n^2$ is even.

Solution Steps
  1. Write an even integer in the form $n=2k$.
  2. Square the expression and show it is twice an integer.
$$n=2k$$ $$n^2=(2k)^2=4k^2=2(2k^2)$$ Since $2k^2$ is an integer, $n^2$ is even.

Contrapositive: An Odd Square

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

Solution Steps
  1. Prove the contrapositive: if $n$ is even, then $n^2$ is even.
  2. Use the definition of an even integer.
$$n=2k\ \Longrightarrow\ n^2=4k^2=2(2k^2)$$ Thus an even $n$ has an even square, so the contrapositive proves the claim.

Contradiction: $\sqrt{2}$ Is Irrational

Assume for contradiction that $\sqrt{2}=a/b$ in lowest terms, where $a,b$ are integers and $b\ne0$.

Solution Steps
  1. Square the assumed fraction and conclude that $a^2$ is even.
  2. Then $a$ is even; substitute $a=2k$ to show $b$ is even too.
  3. This contradicts that $a/b$ was in lowest terms.
$$2=\frac{a^2}{b^2}\quad\Longrightarrow\quad a^2=2b^2$$ So $a^2$ is even and therefore $a$ is even; write $a=2k$. $$4k^2=2b^2\quad\Longrightarrow\quad b^2=2k^2$$ Then $b$ is even as well. Both numerator and denominator are even, a contradiction.

Disprove a Claim

Disprove the claim “Every prime number is odd.”

Solution Steps
  1. A universal claim needs only one counterexample to fail.
  2. Check the smallest prime.
$$2\text{ is prime, but }2\text{ is even.}$$ Therefore the claim is false.