Proving a recursion right: induction

Assume the smaller calls are already right, show the step is right, and check that the input really is getting smaller.

A recursive procedure has no loop to hang an invariant on. It calls itself, and the argument that it is right has a different shape: assume the calls it makes are already correct, then show that what it does with their answers is correct. That sounds circular and is not, provided the calls are on genuinely smaller inputs.

Here is a procedure that adds up a list by taking the first value and asking itself for the sum of the rest. The printing shows the calls going down and the answers coming back up.

Read the output bottom upwards and the structure is visible. The deepest call answers without asking anyone. Every other call takes one answer from below, adds one number to it, and passes it up. Nothing in that chain checks the whole list; each link only has to be right about its own single addition.

What induction is

Mathematical induction proves a statement $P(m)$ for every whole number $m$ from 0 upwards, using two pieces. First a base case: show $P(0)$ directly. Then an inductive step: show that if $P(m-1)$ is true then $P(m)$ is true, for every $m$ greater than 0. The assumption you are allowed to make inside the step is called the induction hypothesis.

Together they reach every number. $P(0)$ is proved outright. The step turns $P(0)$ into $P(1)$, then $P(1)$ into $P(2)$, and so on, so no number is left out. Strong induction is the same thing with a more generous hypothesis: in proving $P(m)$ you may assume $P(k)$ for every $k$ smaller than $m$, not only for $m-1$. You need it whenever a procedure calls itself on something more than one step smaller.

For a recursive procedure, the statement being proved is normally the procedure's own contract, and the number being inducted on is the size of the input that call was given. Here is the whole argument for the sum above.

Let $m$ be the number of positions left, that is $m = n - i$ where $n$ is the length of the list. The claim $P(m)$ is: total_from(a, i) returns the sum of the values at positions $i$ to $n-1$, and returns it after finitely many calls.

• Base case, $m = 0$. Then $i$ equals $n$, the test i == len(a) succeeds, and the procedure returns 0 with no further calls. The sum of no values is 0, so the claim holds.
• Inductive step, $m > 0$. Then $i < n$, so the test fails and the procedure calls itself with $i + 1$, which leaves $m - 1$ positions. By the induction hypothesis $P(m-1)$, that call returns the sum of positions $i+1$ to $n-1$, after finitely many calls. Name that value $S$. The procedure returns a[i] + S. The sum of positions $i$ to $n-1$ is the value at position $i$ plus the sum of positions $i+1$ to $n-1$, which is exactly a[i] + S. And it made one call more than a finite number, which is finite. So $P(m)$ holds.
• Conclusion. $P(m)$ holds for every $m \ge 0$, so in particular for $m = n$ with $i = 0$, which is the call the caller makes.

The third condition is the one that bites

The size the recursion shrinks is called the measure. It has to strictly decrease at every call and it has to be caught by a base case before it can run past the bottom. Decreasing on its own is not enough, and the next snippet shows why. It counts its own calls and gives up once it has made a dozen, so that you can see the failure rather than wait for it.

Starting from 7 the argument goes 7, 5, 3, 1, -1, -3, and never lands on 0. The measure decreases by 2 every time, which satisfies the letter of the rule, and the base case only catches one exact value, so the recursion steps straight over it. Without the call counter this program would run until the machine ran out of room to remember where each call came from.

When one call is not enough to assume

Some recursions make more than one call, or call themselves on an input more than one step smaller. Then the plain hypothesis $P(m-1)$ is not enough and you use strong induction. The Fibonacci numbers are the standard case: $F_0 = 0$, $F_1 = 1$, and $F_m = F_{m-1} + F_{m-2}$ for $m \ge 2$.

The proof needs two base cases, because there are two calls that answer without recursing. $P(0)$: the procedure returns 0, which is $F_0$. $P(1)$: it returns 1, which is $F_1$. For the step, take $m \ge 2$ and assume $P(k)$ for every $k$ with $0 \le k < m$. Both $m-1$ and $m-2$ are in that range, so the two calls return $F_{m-1}$ and $F_{m-2}$, and their sum is $F_m$ by the definition. The measure is $m$ itself: both calls lower it, and the base cases catch 0 and 1, so nothing steps past the floor.