Solving Recurrence Relations

(Adapted from Mathematical Structures for Computer Science, 4th edition, Judith Gersting, Freeman.)

A sequence is a list of objects that are enumerated in some order. A sequence may be defined recursively, that is, the nth term may be defined using one or more previous terms. Such a recursive rule is called a recurrence relation. For example, the fibonacci sequence may be defined as follows: 

fib(1) = 1
fib(2) = 2
fib(n) = fib(n-1) + fib(n-2)
Note that in addition to the recurrence relation (the third rule), there are two base cases (the first two rules). As for any recursive definition, at least one base case is always required. Although technically fib is defined by two base cases and one recurrence relation, we may loosely refer to the entire definition of fib as a recurrence relation.

Finding Closed Form Solutions

It is often inconvenient to find the nth term of a sequence that is defined by a recurrence relation, as doing so requires finding previous terms in the sequence as well. Sometimes we can find a non-recursive definition, or closed form solution, for the same sequence. For example, consider the sequence S below: 
S(1) = 2
S(n) = 2S(n-1)
If we look at a few terms, we see that S(1)=2, S(2)=4, S(3)=8, S(4)=16, and so on -- in general S(n) = 2n. We say that S(n) = 2n is a closed form solution for S.

But it is not always this easy to find a closed form solution. (Sometimes it isn't even possible.) For more difficult cases, it's useful to formalize the process above into three steps:

Example

Suppose we are building a line of squares out of matchsticks. We can build one square using four matchsticks: 
             -
            | |
             -
Adding a second square requires 3 more matchsticks: 
             - -
            | | | 
             - -
Adding another square would take 3 more matchsticks, and so on. If M(n) represents the number of matchsticks required to make n squares, we could define M as follows: 
M(1) = 4
M(n) = 3 + M(n-1)
To find a closed form solution for M, we first expand the recurrence relation a few times and look for a pattern: 
M(n) = 3 + M(n-1)
     = 3 + (3 + M(n-2)) = 3 + 3 + M(n-2)
     = 3 + 3 + (3 + M(n-3)) = 3 + 3 + 3 + M(n-3)
Stopping at this point, we see that at each step we are adding together some number of 3s and subtracting that same number from n in the index for M. (Note that we didn't actually do the addition to make 3+3=6 and 3+3+3=9; sometimes it's easier to see a pattern without the addition, sometimes with. Often you'll need to try both.) Calling that number k, we could generalize this as follows: 
M(n) = 3k + M(n-k)  k>=1
To find a closed form solution we need to get rid of M(n-k) -- we want a definition for M(n) that does not rely on M. The only way to get rid of M(n-k) is to get it down to the base case so that we can substitute a non-recursive definition. The base case is defined for n=1, so if we let k=n-1, we will get what we want: 
M(n) = 3(n-1) + M(n-(n-1))
     = 3n-3 + M(1)
     = 3n-3 + 4
     = 3n+1.
This is our guess: M(n) = 3n+1.

Verifying a guess

We can verify that M(n) = 3n+1, n>=1, is a solution for the recurrence relation M as defined above using the familiar technique of mathematical induction: 
Base case: (n=1) By def of M, M(1)=4.  Using guess, M(1) = 3*1+1=4.

Inductive step: If M(k) = 3k+1 then M(k+1) = 3(k+1)+1 = 3k+4.

Proof:
By the definition of M, M(k+1) = 3 + M(k).  
By the inductive hypothesis M(k) = 3k+1.
Substituting this in above we get M(k+1) = 3 + 3k+1
                                         = 3k + 4, which is what we wanted to show.

Another Example

Consider the recurrence T below: 
T(1) = 1
T(n) = 1 + T(n/2)
To look for a closed form solution, we first expand the recurrence relation: 
T(n) = 1 + T(n/2)
     = 1 + (1 + T(n/4)) = 2 + T(n/4)
     = 2 + (1 + T(n/8)) = 3 + T(n/8)
     = 3 + (1 + T(n/16)) = 4 + T(n/16)
A pattern is emerging: at each step we have T(n) = k+T(n/2k) for some k>=1. To remove the T term we again need to get it down to the base case, which means we need to get n/2k=1. This requires that 2k=n, or k=log2n. Substituting this in for k in our generalized equation above, we get 
T(n) = log2n + T(n/2log2n)
     = log2n + T(n/n)
     = log2n + T(1)
     = log2n + 1.
This is our guess.

To verify that given the definition of T above, T(n)=log2n+1, n>=1, we again use mathematical induction. But since the nth term of T depends not on the n-1 term but on the n/2 term, we need to use the second principle in setting up the inductive step. 

Base case: (n=1) By def of T, T(1)=1.  Using guess, T(1) = log21+1 = 0+1 = 1.

Inductive step: If T(r) = log2r+1, 1<=r<=k, then T(k+1) = log2(k+1)+1.

Proof:
By the definition of T, T(k+1) = 1 + T((k+1)/2)
By the inductive hypothesis T((k+1)/2) = log2((k+1)/2)+1.  (Note that (k+1)/2 will always be between 1 and k, 
so we can safely apply the inductive hypothesis.)
Substituting this in above we get T(k+1) = 1 + log2((k+1)/2)+1
                                         = 2 + log2((k+1)/2)
                                         = 2 + log2(k+1) - log22 (remember log(a/b)=log a-log b)
                                         = 2 + log2(k+1) - 1
                                         = log2(k+1) +1, which is what we wanted to show.