Proof Techniques

A proof is a chain of logically valid steps from accepted facts to a conclusion. Proofs are how we know an algorithm is correct for all inputs, not just the ones we tested.

#Rules of inference

#Direct proof

To prove p → q: assume p, then use definitions and known facts to reach q.

Theorem. If n is odd, then n² is odd. Proof. Suppose n is odd, so n = 2k + 1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ∎

#Proof by contrapositive

Prove ¬q → ¬p instead, which is equivalent to p → q. Use it when the negations are easier to work with.

Theorem. If n² is even, then n is even. Proof. Contrapositive: if n is odd, then n² is odd — proved above. ∎

#Proof by contradiction

Assume the statement is false and derive something impossible.

Theorem. √2 is irrational. Proof. Suppose √2 = a/b in lowest terms. Then 2b² = a², so a² is even, so a is even: a = 2c. Then 2b² = 4c², so b² = 2c² is even, so b is even. But then a and b share the factor 2, contradicting "lowest terms". ∎

Theorem (Euclid). There are infinitely many primes. Proof. Suppose there are finitely many: p₁, p₂, …, pₙ. Let N = p₁p₂…pₙ + 1. No pᵢ divides N (each leaves remainder 1), so N's prime factors are not in the list — a contradiction. ∎

#Proof by cases

Split into cases that cover every possibility and prove each one.

Theorem. n² + n is even for every integer n. Proof. If n is even, n² and n are both even, so their sum is even. If n is odd, n² and n are both odd, and odd + odd is even. ∎

#Counterexamples

To disprove a universal statement ∀x P(x), one counterexample is enough.

Claim: "n² + n + 41 is prime for every n ≥ 0." It holds for n = 0 … 39, but fails at n = 40. Testing many cases is evidence, never proof:

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

for n in range(45):
    if not is_prime(n * n + n + 41):
        print(f"counterexample: n = {n}, n^2 + n + 41 = {n*n + n + 41} = 41 x {(n*n + n + 41) // 41}")
        break
else:
    print("no counterexample found")

counterexample: n = 40, n^2 + n + 41 = 1681 = 41 x 41

#Existence proofs

• Constructive: exhibit the object. "There is an integer that is the sum of two cubes in two ways": 1729 = 1³ + 12³ = 9³ + 10³.
• Non-constructive: show it must exist without naming it (often by contradiction or the pigeonhole principle).

#Which technique?