Proofs and counterexamples

A proof is an argument that shows a statement is true in every case, step by step from definitions and facts already proved. A statement with a proof is a theorem.

Examples are not proofs

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

# n² + n + 41 is prime for n = 0 to 39. Check the last few, and the next one.
for n in range(37, 42):
    value = n * n + n + 41
    print(n, value, "prime" if is_prime(value) else "NOT prime")

The formula n² + n + 41 gives a prime for n = 0, 1, 2, ..., all the way to 39: forty primes in a row. It would be easy to believe it always does. But for n = 40 it gives 1681 = 41 × 41. Checking cases builds confidence and can find counterexamples, but it never proves a "for all" statement about infinitely many numbers.

Direct proof

To prove p → q: assume p, and reason until you reach q.

Theorem. If n is odd, then n² is odd.

Proof. n is odd, so n = 2k + 1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is 2 times an integer plus 1, so n² is odd. ∎

The definitions do the work: even means "= 2k", odd means "= 2k + 1", for some integer k.

Proof by contrapositive

p → q is equivalent to ¬q → ¬p, and sometimes that is easier to prove.

Theorem. If n² is even, then n is even.

Proof. We prove the contrapositive: if n is not even (odd), then n² is not even (odd). That is the theorem we just proved. ∎

Proof by contradiction

To prove p: assume ¬p, and reason until you reach something impossible. Then ¬p was wrong, so p is true.

Theorem. √2 is irrational.

Proof. Suppose √2 = a/b, a fraction in lowest terms (a and b have no common factor). Then 2 = a²/b², so a² = 2b², which is even. By the last theorem, a is even: a = 2c. Then 4c² = 2b², so b² = 2c² is even, and b is even too. But then a and b have the common factor 2, which contradicts "lowest terms". So √2 is not a fraction. ∎

Disproving with a counterexample

A "for all" statement is false as soon as one case fails. "Every prime is odd" is false: 2 is prime and even. Finding counterexamples is where computers shine:

# Claim: 2ⁿ - 1 is prime whenever n is prime. Search for a counterexample.
def is_prime(n):
    if n < 2:
        return False
    return all(n % d != 0 for d in range(2, int(n ** 0.5) + 1))

for n in [2, 3, 5, 7, 11]:
    value = 2 ** n - 1
    if not is_prime(value):
        print(f"counterexample: n = {n}, 2^{n} - 1 = {value} = 23 × 89")
        break
    print(f"n = {n}: {value} is prime")

Mark lesson complete