Proof techniques
A proof is an argument that leaves no room for doubt. A small set of strategies covers most proofs you will meet.
What a proof is
A proof establishes a statement using definitions, axioms, and previously proved results, with each step following logically. Unlike evidence from examples, a proof covers every case. Checking that \(n^2 + n + 41\) is prime for \(n = 0\) to \(39\) proves nothing: it fails at \(n = 40\).
Direct proof
To prove \(p \to q\) directly, assume \(p\) and reason step by step to \(q\). Claim: the sum of two even integers is even. Let \(a = 2m\) and \(b = 2n\). Then \(a + b = 2(m + n)\), which is even. Writing definitions in algebraic form is usually the first move.
Proof by contrapositive
Prove \(\neg q \to \neg p\) instead. Claim: if \(n^2\) is even, then \(n\) is even. Contrapositive: if \(n\) is odd, then \(n^2\) is odd. With \(n = 2k + 1\), \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), odd. Use the contrapositive when the negated statements are easier to work with.
Proof by contradiction
Assume the statement is false and derive something impossible. Classic example: \(\sqrt{2}\) is irrational. Suppose \(\sqrt{2} = \frac{a}{b}\) in lowest terms. Then \(a^2 = 2b^2\), so \(a\) is even, \(a = 2c\), giving \(b^2 = 2c^2\), so \(b\) is even too, contradicting lowest terms. So \(\sqrt{2}\) is irrational.
Proof by cases
Split into exhaustive cases and prove each. Claim: \(n^2 + n\) is even for every integer \(n\). Case 1: \(n\) even, then \(n^2\) and \(n\) are even, so the sum is even. Case 2: \(n\) odd, then both are odd, and odd plus odd is even. Every integer is covered.
Existence and uniqueness
To prove something exists, construct an example or show one must exist. To prove uniqueness, assume two objects have the property and show they are equal. Euclid's proof that there are infinitely many primes is a famous existence-by-contradiction argument: multiply any finite list of primes and add 1, and the result has a prime factor not on the list.
Disproof by counterexample
To show a universal statement is false, give one counterexample. 'Every odd number is prime' fails at 9. Finding counterexamples is often quicker than searching for a proof, so test small cases first.
Writing proofs well
State what you are proving, define your variables, justify each step, and signal the end (often with 'QED' or a box). Write in full sentences. A proof is communication: the reader should be able to follow every step without guessing your reasoning.
Key takeaways
Direct proofs assume the hypothesis and derive the conclusion. Contrapositive proofs prove \(\neg q \to \neg p\). Contradiction assumes the opposite and finds an impossibility. Cases cover every possibility. One counterexample disproves a universal claim, and examples alone never prove one.
Flashcard
A complete logical argument
Check your understanding
To prove 'if n^2 is odd then n is odd', the most natural method is: