Induction: the domino chain

A direct proof works when you can see the whole argument at once, like the case split in the previous lesson. It breaks down the moment the claim contains three dots. The sum one plus two plus three up to n has infinitely many instances, and no page holds infinitely many lines. Writing and so on is not a proof, it is a promise that a proof exists somewhere. Induction is the tool that keeps that promise with finitely many words, and it has exactly two parts.

claim: for every integer n >= 1,

  1 + 2 + 3 + ... + n  =  n * (n + 1) / 2

n = 1    1            = 1
n = 2    1 + 2        = 3
n = 3    1 + 2 + 3    = 6
n = 4    1+2+3+4      = 10

base case:      n = 1
inductive step: if it holds for n, it holds for n + 1

The base case is the claim with the smallest legal n substituted in, checked by hand. The inductive step is a conditional: assuming the claim holds for some n, show that it then holds for n plus one. Notice what the step does not do. It says nothing about whether the claim is true for any particular n. It is a machine that turns a truth at n into a truth at n plus one, and a machine with no input produces no output. Together the two parts give everything: the base case starts the chain, and the step is what carries it forward forever.

Here is why both halves are needed, and it is worth seeing a real failure of each kind rather than taking it on faith. First, the step alone. If you assume n plus one equals n and add one to both sides, you get n plus two equals n plus one, which is the same claim with n replaced by n plus one. The step is perfectly valid. The claim is still false for every n, because no first domino ever fell.

claim A: for every integer n >= 1,  n + 1 = n

step: n + 1 = n
      (n + 1) + 1 = n + 1          holds

base: n = 1  ->  1 + 1 = 1       false

step = T, base = F

Now the other failure: a base case with no working step. The polynomial below was genuinely believed to be prime for all n, and it passes at n equals one. It even survives all the way to n equals 39. At n equals 40 it factors, and the chain stops there. This is the failure mode that finds you in code: one hundred array indices all behave, and index zero or index n minus one was never in the range you tested.

claim B: for every integer n >= 1,  n^2 + n + 41  is prime

base: n = 1   ->  43              prime
step: n = 39  ->  1601            prime
      n = 40  ->  1681 = 41 * 41   composite

base = true, step broken at 39 -> 40

Sometimes assuming only the case n is not enough. If you split a number into two smaller factors, you need to know that both of them factor into primes, and both are smaller than n rather than equal to n minus one. Strong induction assumes the claim for every value below n, which gives you more to work with and is not actually a stronger requirement: anything provable by strong induction is provable by ordinary induction, just with a clumsier statement. The distinction matters in practice because strong induction is the correct shape for divide and conquer.

claim: every integer n >= 2 factors into primes

base:        n = 2 is prime
strong step: assume the claim for every k, 2 <= k < n

  n prime    ->  done
  n = a * b  ->  a < n and b < n
                 T(k) holds for 2 <= k < n

T(n) = T(a) and T(b)

That brings us to the reason this lesson sits in a programming course. Merge sort calls itself twice on halves and merges the results. Students usually accept that it works because they have seen it work. The inductive proof is the actual reason. Base case: an array of length zero or one is sorted, and the function returns it. Step: assume merge sort returns a sorted array for every input shorter than n. Then the two halves come back sorted, and merging two sorted arrays is sorted. By induction the function is correct for arrays of every length. This is not decoration: the base case below is exactly the condition in the if statement, and the step is exactly the correctness of merge.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

# T(1) = c
# T(n) = 2 * T(n / 2) + O(n)
# depth = log2(n), work per level = O(n) -> O(n log n)Recursive merge sort. The base case of the induction is the first line, and the inductive step is the merge.

The same shape gives the running time, and this is where O(log n) finally comes from rather than being a shape you memorise from a graph. At every level of recursion the total work is n, and the number of levels is how many times you can halve n before reaching one element, which is log base 2 of n. Multiply the work per level by the number of levels and you get n log n. Binary search is the sharper case: it does constant work per level and throws away half the data, so the cost is exactly the number of halvings. Doubling the input adds one step, which is why a search over a million elements takes twenty comparisons and not a million. Induction is what makes that sentence true instead of merely observed.

/* sorted array, search space halved */

  1000000  ->  500000  ->  250000  ->  125000  ->  ...

  2^10  = 1024             10 halvings
  2^20  = 1048576          20 halvings

T(1) = 1
T(n) = T(n / 2) + c   ->   T(n) = O(log n)

/* loop invariant over a[0 .. n - 1] */

init:  i = 0,  m = a[0]
test:  while i < len(a):
step:    if a[i] > m: m = a[i]
         i = i + 1
exit:  i == len(a)  ->  m = max(a)