Mathematical induction and recursion

Mathematical induction is the main tool for proving that a statement holds for every natural number, and so for every input size, every list length and every number of loop iterations. It is the mathematical twin of recursion: a recursive function solves a problem by solving a smaller instance, and an inductive proof proves a statement by relying on a smaller instance. This lesson covers ordinary induction, strong induction, recursive definitions and structural induction, and shows how each one proves facts about programs.

The principle of induction

Let \(P(n)\) be a statement about natural numbers. To prove \(\forall n \ge b\, P(n)\), it is enough to prove two things. The base case: \(P(b)\) is true. The inductive step: for every \(k \ge b\), if \(P(k)\) is true then \(P(k+1)\) is true. In the inductive step, the assumption \(P(k)\) is called the inductive hypothesis.

The image of dominoes makes it convincing. The base case knocks over the first domino. The inductive step guarantees that each falling domino knocks over the next. Together they topple every domino, however long the line. Logically, the base case and inductive step give \(P(b)\), then \(P(b+1)\) by modus ponens, then \(P(b+2)\), and so on with no exceptions. Induction is accepted as an axiom about the natural numbers, equivalent to the well-ordering principle: every non-empty set of natural numbers has a least element.

The inductive step is where the work happens, and it always has the same shape: write the statement for \(k+1\), find the statement for \(k\) inside it, replace that part using the inductive hypothesis, and simplify to the required form. If you never used the inductive hypothesis, either the statement was easy without induction or the proof has a gap.

from fractions import Fraction
# Evidence first: check the formulas we will prove for many n
print(all(sum(range(1, n + 1)) == n * (n + 1) // 2 for n in range(1, 2001)))
print(all(sum(i * i for i in range(1, n + 1)) == n * (n + 1) * (2 * n + 1) // 6 for n in range(1, 2001)))
print(all(sum(2 ** i for i in range(n + 1)) == 2 ** (n + 1) - 1 for n in range(0, 200)))
print(all(sum(Fraction(1, i * (i + 1)) for i in range(1, n + 1)) == Fraction(n, n + 1) for n in range(1, 200)))

True
True
True
True

Induction for inequalities and divisibility

Induction is not only for sums. In lesson 1 we explored the claim \(2^n > n^2\) and found it holds from \(n = 5\). Induction proves it, with the base case at 5.

Strong induction

In ordinary induction, the step from \(k\) to \(k+1\) uses only \(P(k)\). In strong induction, the step may use \(P(b), P(b+1), \ldots, P(k)\): all earlier cases. Strong induction is no more powerful logically, but it is far more convenient when \(P(k+1)\) depends on a case several steps back, as happens with recursive algorithms that split a problem in half or with sequences defined by more than one earlier term.

def stamps(n):
    """Return (fours, fives) with 4*fours + 5*fives == n, or None."""
    for fives in range(n // 5 + 1):
        rest = n - 5 * fives
        if rest % 4 == 0:
            return rest // 4, fives
    return None

print("cannot make:", [n for n in range(1, 12) if stamps(n) is None])
for n in [12, 13, 14, 15, 16, 31, 100]:
    print(n, "=", stamps(n))
print("all of 12..10000 possible:", all(stamps(n) for n in range(12, 10001)))

cannot make: [1, 2, 3, 6, 7, 11]
12 = (3, 0)
13 = (2, 1)
14 = (1, 2)
15 = (0, 3)
16 = (4, 0)
31 = (4, 3)
100 = (25, 0)
all of 12..10000 possible: True

Recursive definitions

A recursive definition defines an object in terms of smaller versions of itself. It has two parts, just like an inductive proof: base cases, and a recursive rule. The factorial function is defined by \(0! = 1\) and \(n! = n \cdot (n-1)!\) for \(n \ge 1\). The Fibonacci numbers are defined by \(F_0 = 0\), \(F_1 = 1\) and \(F_n = F_{n-1} + F_{n-2}\) for \(n \ge 2\). Because recursive definitions build each value from earlier ones, induction is the natural way to prove things about them.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib(n) for n in range(15)])
print("F_n < 2^n for n < 500:", all(fib(n) < 2 ** n for n in range(500)))
phi = (1 + 5 ** 0.5) / 2
for n in (10, 20, 30):
    print(f"F_{n} = {fib(n):7d}   phi^{n}/sqrt(5) = {phi ** n / 5 ** 0.5:10.1f}")

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
F_n < 2^n for n < 500: True
F_10 =      55   phi^10/sqrt(5) =       55.0
F_20 =    6765   phi^20/sqrt(5) =     6765.0
F_30 =  832040   phi^30/sqrt(5) =   832040.0

Recursion and induction are the same idea

A recursive function is correct for exactly the reason an inductive proof works. To show that a recursive function returns the right answer for every input, prove by induction on the input size: the base case of the function returns the right answer, and if every recursive call on a smaller input returns the right answer (the inductive hypothesis), then the combination step produces the right answer.

A faster version, fast exponentiation, computes \(x^n\) by squaring: if \(n\) is even, \(x^n = (x^{n/2})^2\); if odd, \(x^n = x \cdot x^{n-1}\). Its correctness proof needs strong induction, because the recursive call is on \(n/2\), not \(n - 1\). This algorithm makes RSA encryption practical, as lesson 11 shows.

def fast_pow(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = fast_pow(x, n // 2)      # strong induction: n // 2 < n
        return half * half
    return x * fast_pow(x, n - 1)

calls = 0
def counted(x, n):
    global calls
    calls += 1
    if n == 0: return 1
    if n % 2 == 0:
        h = counted(x, n // 2); return h * h
    return x * counted(x, n - 1)

print(all(fast_pow(3, n) == 3 ** n for n in range(200)))
counted(3, 1000)
print("calls for n = 1000:", calls, " versus 1001 for the simple version")

True
calls for n = 1000: 16  versus 1001 for the simple version

Structural induction

Many data structures are defined recursively. A list is either empty or an element followed by a list. A binary tree is either empty or a node with a left subtree and a right subtree. Structural induction proves a property for every such structure: prove it for the base structures, then prove that whenever the parts have the property, the structure built from them does too.

Common pitfalls

Induction proofs go wrong in predictable ways. The most famous fake proof claims that all horses are the same color. The base case, one horse, is fine. The inductive step takes a set of \(k+1\) horses, removes one to get \(k\) horses of the same color, removes a different one to get another \(k\) horses of the same color, and argues that the two groups overlap, so all \(k+1\) match. The overlap argument fails when \(k + 1 = 2\): the two groups of one horse each do not overlap. The step from 1 to 2 is broken, so the whole chain collapses.