Proof by induction

Many claims in this course are about every size of input: every list, every n. You cannot check them all one by one. Induction proves such a claim with two short arguments.

Proving a claim for every n

Suppose you have a claim about a whole number n, written P(n). To prove that P(n) is true for every n of 1 or more, prove two things:

1. Base case. P(1) is true.
2. Inductive step. For any k of 1 or more: if P(k) is true, then P(k + 1) is true.

Why is that enough? The base case gives P(1). The step, used with k = 1, then gives P(2). Used again with k = 2, it gives P(3). This continues with no gaps, so every n is reached.

In the step, you assume P(k) and use it. This assumption is called the inductive hypothesis. It is allowed: you are not assuming the whole claim, only that it holds for one value of k, and showing that it then also holds for the next.

Example: adding odd numbers

Claim: 1 + 3 + 5 + … + (2n − 1) = n². In words, the first n odd numbers add up to n squared, n × n. Step through the figure first: it builds the sum as a square, one odd number at a time.

Now the proof in words:

• Base case. For n = 1, the sum is 1, and 1² = 1.
• Step. Assume the first k odd numbers add up to k². The next odd number is 2k + 1. So the first k + 1 odd numbers add up to k² + 2k + 1, which is (k + 1)².

Strong induction

Sometimes P(k + 1) depends not on P(k) but on some smaller case, such as P(k / 2). Then use strong induction: in the step, assume the claim for every value from 1 to k, not only for k. It is just as valid, and it fits algorithms that cut a problem in half.

Example. Claim: every whole number n of 2 or more can be written as a product of primes. If n is prime, it is its own product. If not, then n = a × b with both a and b between 2 and n − 1. By the strong hypothesis, both a and b are products of primes, so n is too.

Induction proves recursive code

A recursive function calls itself on a smaller input. Proving it correct is induction on the size of the input: the base case of the proof is the base case of the code.

def power(x, n):
    """Promise: returns x to the power n, for any whole n >= 0."""
    if n == 0:
        return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

• Base case. n = 0: it returns 1, and x⁰ = 1 (x to the power 0 is 1).
• Step (strong). Take n of 1 or more, and assume the function is correct for every smaller power. Then half is x to the power ⌊n/2⌋, where ⌊ ⌋ means round down. If n is even, n = 2⌊n/2⌋, so half * half is xⁿ, n copies of x multiplied together. If n is odd, n = 2⌊n/2⌋ + 1, so one more * x is needed.

Notice what the proof did not do. It never followed the calls down to the bottom. It assumed that the smaller call is correct, because the hypothesis allows that. This is how to think about recursion in RECR: assume the smaller call is correct, and check only one level.

Common mistakes