Proof Techniques

Study Sheet

Proof Techniques

How to structure a rigorous argument

The Main Forms

Tip
Direct, contradiction, contrapositive

To prove P⇒QP\Rightarrow Q: argue directly; or assume PP and ¬Q\lnot Q and reach a contradiction; or prove the contrapositive ¬Q⇒¬P\lnot Q\Rightarrow\lnot P.

In plain terms. There are three standard ways to prove "if P then Q." Pick whichever gives you the most concrete facts to start from.

Example. To show 2\sqrt2 is irrational, assume it equals p/qp/q in lowest terms (contradiction) and derive that p,qp,q are both even.

Tip
Induction, weak and strong

Prove a base case, then show it for nn (weak) — or for all values below nn (strong) — implies it for n+1n+1.

In plain terms. Knock over the first domino, then show each domino knocks over the next, and they all fall.

Example. Prove 1+3+⋯+(2n−1)=n21+3+\cdots+(2n-1) = n^2: true at n=1n=1, and adding 2n+12n+1 to n2n^2 gives (n+1)2(n+1)^2.

Concept
Well-ordering / minimal counterexample

Every nonempty set of positive integers has a least element, so assuming a smallest counterexample and building a smaller one is a contradiction.

In plain terms. If something could fail, look at the smallest case where it fails — then show you could make an even smaller one, which is impossible.

Example. To prove every n>1n>1 has a prime factor: the smallest divisor above 11 must itself be prime, or it would have a smaller one.