The Art and Craft of Problem Solving

4.3 GENERATING FUNCTIONS 135

This is the generating function of the original sequence, but shifted. In other words,
the coefficient of XZ in f(x) is an, while the coefficient of XZ inxf(x) is an-I. Now we
make use of the relationship between an and an-I. Since an -3an-I = 2 for all n 2 I,
we have

f(x) -^3 xf(x) = ao +2(x+� +x^3 + ... ).

That looks ugly, but the expression in parentheses on the right-hand side is just an
infinite geometric series. Thus we have (remember, ao = I)

2 x

f(x) - 3xf(x) = 1 +

I - x

.

The left-hand side is f(x)(1 - 3 x), so we can easily solve for f(x), getting

1 2x

f(x) =

1-3x

+

(I-x)(1 - 3 x)

x+I

(^1 - x)(1 -^3 x)

·

Our goal is somehow to recover the coefficients when f(x) is expanded in a power

series. If the denominators were just (1 - x) or (1 - 3 x), we could use the geometric

series tool. Partial fractions^7 comes to the rescue, yielding

x+I

f(x) =

(l-x)(1- 3x)

2

1-3x I-x

Using the geometric series tool on the first term, we get

And since

we get

(^1 2 1)
--=I+x+x +.r + ... ,

I-x

f (x) = 2(1 + 3x+3^2 � + 3^3 x^3 + ... ) - (1 +x+� +x^3 + ... )

= 1 + (2·3 - I)x + (2. 32 - I)� + ( 2. 33 - 1 )x^3 + ... ,

from which it follows immediately that an = 2· 3 n - 1. •

This method was technically messy, since it involved using the geometric-series

tool repeatedly as well as partial fractions. But don't get overwhelmed by the tech­

nical details-it worked because mUltiplying a generating function by x produced the

generating function for the "shifted" sequence. Likewise, dividing by x will shift the

sequence in the other direction. These techniques can certainly be used for many kinds

of recurrences.

(^7) If you don't remember this technique, consult any calculus text. The basic idea is to write (
I �ti^3 x) =
4 + I�X and solve for the unknown constants A and B.