Proofs with recursion and induction

When working with recursive definitions and algorithms, it is important to be able to prove that they actually do the right thing. The natural method for this is mathematical induction. Induction resembles recursion: one starts with a base step and then shows that if the statement holds for one step, it also holds for the next.

 

 

Example 1: Factorial

We want to prove that the recursive definition of factorial corresponds to the usual product formula:

 

$$ \large n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \quad n \geq 1 $$

 

Base

 

For \( \large n = 1 \):

 

$$ \large 1! = 1 \quad \text{holds} $$

 

Induction step

 

Assume that the statement holds for a particular \( \large n \), that is

 

$$ \large n! = 1 \cdot 2 \cdot \ldots \cdot n $$

 

Then we get for \( \large n+1 \):

 

$$ \large (n+1)! = (n+1) \cdot n! $$

 

By the induction hypothesis we can replace \( \large n! \):

 

$$ \large (n+1)! = (n+1) \cdot (1 \cdot 2 \cdot \ldots \cdot n) $$

 

Thus we obtain exactly the product up to \( \large n+1 \). Hence the statement holds for all \( \large n \).

 

 

Example 2: Fibonacci

The Fibonacci sequence is defined by

 

$$ \large F_{0} = 0, \quad F_{1} = 1, \quad F_{n} = F_{n-1} + F_{n-2} \;\; (n \geq 2) $$

 

A known formula states that the sum of the first \( \large n \) Fibonacci numbers is:

 

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

 

Base

For \( \large n = 0 \) we have on the left only the sum \( \large F_{0} = 0 \).

On the right we have \( \large F_{2} - 1 = 1 - 1 = 0 \).

Both sides give the same result, so the statement holds in the base case.

 

Induction step

Assume that the statement holds for a particular \( \large n \):

 

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

 

We show it for \( \large n+1 \):

 

$$ \large F_{0} + F_{1} + \ldots + F_{n} + F_{n+1} $$

$$ \large = (F_{n+2} - 1) + F_{n+1} \quad \text{(by the induction hypothesis)} $$

$$ \large = F_{n+1} + F_{n+2} - 1 $$

$$ \large = F_{n+3} - 1 $$

 

Thus the statement also holds for \( \large n+1 \). By induction the formula holds for all \( \large n \).

 

 

Example 3: Correctness of a recursive algorithm

Earlier we saw the algorithm that finds the maximum in a list:

 

function max(list):
    if list has length 1:
        return list[0]            // base
    else:
        m = max(rest of list)     // recursive step
        return the larger of list[0] and m

 

We want to prove that the algorithm always returns the largest element in the list.

 

Base

If the list has length 1, the algorithm returns the only element. This is correct, since a single element is obviously the maximum.

 

Induction step

Assume that the algorithm works correctly for all lists of length \( \large n \). We must then show that it also works for a list of length \( \large n+1 \).

 

Let the list be \( \large [x_0, x_1, \ldots, x_n] \). The algorithm calls itself on the sublist \( \large [x_1, \ldots, x_n] \), which has length \( \large n \). By the induction hypothesis this call returns the correct maximum of the sublist.

 

Finally, the algorithm compares this maximum with the first element \( \large x_0 \). Thus the maximum of all elements \( \large x_0, x_1, \ldots, x_n \) is returned, that is, the maximum of the entire list.

 

Conclusion

By induction, the algorithm max always returns the largest element in a list, regardless of its length.

 

 

Summary

Induction is the natural method for proving the correctness of recursive definitions. One shows that the base case is valid, and that if the statement holds for one step, it also holds for the next. Thus the entire infinite construction is covered. This makes induction a fundamental tool in working with recursion.