Mathematical induction

Mathematical induction proves that a statement P(n) is true for every whole number n ≥ 1 in two steps:

1. Base case: prove P(1).
2. Inductive step: prove that if P(k) is true (the inductive hypothesis), then P(k + 1) is true, for every k ≥ 1.

Then P(1) is true; so P(2) is; so P(3) is; and so on forever. Think of dominoes: the first one falls, and each falling domino knocks over the next, so they all fall.

An example

Theorem. 1 + 2 + 3 + ... + n = n(n + 1)/2 for every n ≥ 1.

Base case. n = 1: the left side is 1, and the right side is 1 × 2 / 2 = 1. ✓

Inductive step. Assume 1 + 2 + ... + k = k(k + 1)/2. Then

1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)      by the hypothesis
                          = (k + 1)(k/2 + 1)
                          = (k + 1)(k + 2)/2

which is the formula with n = k + 1. ∎

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

total = 0
for n in range(1, 7):
    total += n                        # 1 + 2 + ... + n, added up
    print(n, total, formula(n), total == formula(n))

# The inductive step's algebra: formula(k) + (k + 1) == formula(k + 1)
print(all(formula(k) + (k + 1) == formula(k + 1) for k in range(1, 30)))

The program checks the formula for the first few n, and also checks the inductive step's algebra numerically. That is a useful way to catch a mistake, but only the two steps above are the proof.

Strong induction

Sometimes P(k + 1) needs more than P(k). Strong induction lets the inductive step assume P(1), P(2), ..., P(k) all at once.

Theorem. Every whole number n ≥ 2 is a product of primes.

Proof. Base case: 2 is prime. Step: take k + 1. If it is prime, done. If not, k + 1 = a × b with 2 ≤ a, b ≤ k, and by the hypothesis a and b are products of primes, so their product is too. ∎

Induction and recursion

Induction and recursion are the same idea, seen from two sides. A recursive function is correct if its base case is correct and each recursive call, assuming the smaller calls are correct, builds the right answer. That is an induction proof about the program.

Mark lesson complete