Proofs and induction

A proof is a chain of steps where every step follows from the previous one, and the conclusion therefore has to be true.

Four forms of proof you need to recognise:

Form	The idea	Used for
Direct	assume the premise, work out the conclusion	most things
Counterexample	find a single case where the claim is false	disproving
Contradiction	assume the opposite, derive something absurd	«there is no …»
Induction	show the first case, show that each case gives the next	claims about every n

Induction is the dominoes: show that the first one falls, and that each one knocks over the next. Then all of them fall.

Why a programmer cares: a proof by induction and a recursive function have exactly the same structure. The base case in the code is the base case in the proof; the recursive call is the induction step. If you can write one you can read the other.

A proof by induction in three steps. The claim: $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$.

1. The base case ($n = 1$): the left-hand side is 1, the right-hand side $\frac{1\cdot2}{2} = 1$. ✓

2. The induction hypothesis: assume the formula holds for some $n = k$, that is, $1 + \dots + k = \frac{k(k+1)}{2}$.

3. The induction step: show that it then holds for $k+1$.

$1 + \dots + k + (k+1) = \underbrace{\frac{k(k+1)}{2}}_{\text{the hypothesis}} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

The last expression is precisely the formula with $k+1$ substituted in. ∎

Proof by contradiction. The claim: $\sqrt{2}$ is irrational.

Assume the opposite: $\sqrt{2} = p/q$ in lowest terms. Then $2q^2 = p^2$, so $p^2$ is even, and therefore $p$ is even, say $p = 2m$. Then $2q^2 = 4m^2$, so $q^2 = 2m^2$, and therefore $q$ is even too. But then the fraction would not have been in lowest terms. A contradiction. ∎

One counterexample is enough to falsify. «All primes are odd» falls on $2$. It is the same logic as negating a quantifier: the opposite of $\forall x\,P(x)$ is $\exists x\,\neg P(x)$.

Common errors in proofs by induction:

Error	Why it is wrong
Forgetting the base case	the dominoes never fall over
Assuming what you are to show	a circular proof
Assuming it for every $n$ instead of one	then you have assumed the conclusion
Verifying a few cases and calling it a proof	three cases are not all cases

# Induction and recursion have the same structure
def total(n):
    if n == 1:            # the base case — the same as the proof's base case
        return 1
    return total(n - 1) + n     # the induction step: assume n-1 holds

def formula(n):
    return n * (n + 1) // 2

assert all(total(n) == formula(n) for n in range(1, 500))
print("holds for n = 1..499")

# But: checking is not proving.
# The claim: n² + n + 41 is always a prime.
def is_prime(x):
    return x > 1 and all(x % d for d in range(2, int(x ** 0.5) + 1))

print(all(is_prime(n**2 + n + 41) for n in range(40)))       # True  — 40 cases hold!
print(is_prime(40**2 + 40 + 41))                              # False — a counterexample
print(40**2 + 40 + 41, "=", 41 * 41)                          # 1681 = 41 · 41

# Look for counterexamples systematically — a good habit before trying to prove
def first_counterexample(claim, at_most=10_000):
    return next((n for n in range(1, at_most) if not claim(n)), None)

print(first_counterexample(lambda n: is_prime(n**2 + n + 41)))   # 40

The example with $n^2 + n + 41$ is classic precisely because it holds for the first forty numbers. Testing is excellent for finding errors, but it can never show that no error exists — which is the whole difference between testing and proving, in programming just as much as in mathematics.