COS 341, October 15, 1997

Handout Number 11

Solving Recurrence with Generating Functions

The first problem is to solve the recurrence relation system , and for .

Let . Multiply both side of the recurrence by and sum over . This gives

Note that

Thus, in term of A(x), we obtain

Rearranging terms, we get

Hence,

We can now get by expanding A(x) as a series

This gives, for all ,

This is the same answer as we obtained earlier by different means.

The next problem for solution is the Rabbit Island problem. Before studying it, let us note the following identity, valid for any distinct numbers b and c:

It can be directly verified by taking common denominators of the terms on the right-hand-side, and simplyfing the expression. A more systematic way to do this is to solve the system of equations for variables ,

The solution satisfyies the equation

and gives

This is a special case of the partial fraction decomposition. You might find it challenging to extend the discussion to show that, if b,c,d are distinct,

with sosme appropriate choice of .

In the Rabbit Island problem, we need to solve the recurrence , and for . Let . As in the previous problem, let us multiply the recurrence by and sum over . This gives

In terms of A(x), we have . This leads to

It remains to expand A(x) into a power series, so that we can identify .

Now note that

where and . Using (1) and (2), we can expand A(x) as

Thus, for all , we have

For n=0,1, this formula gives , , as was to be expected.

The numbers are called Fibonacci numbers, and often denoted by . Note that and . Thus, is numerically a very small number, while is large. For reasonably large n, say n>10, can be obtained by evaluating , and rounding it to the closest integer.

The third problem we tackle is the recurrence , , and for . The quantity is the number of ways to parenthesize an expression .

Let . The recurrence relation gives

This means , and hence . Solving the quadratic equation for A(x), we obtain two possible solutions: and . The former solution can be discarded, since it would give , which contradicts our assumption . Thus,

We infer from it , and for ,

Note that, for

This leads to

for . The above formula also holds for n=1 since both sides are equal to 1. (Recall .) The numbers are often called the Catalan numbers.

• About this document ...