CS 171 Generating Function Example

Solve

=

The answer should be

=

=

It is easier if we extend this back to

We can use

=

since the recurrence would then give

=

=

Let

=

(the generating function for the sequence)

Write the recurrence in terms of k:

=

Multiply both sides by

=

Sum both sides

=

Add

to both sides

=

(which is just 0)

Let m = k - 1.

=

Let m = k - 1 again.

=

Find the sum in the
table of generating
functions.

=

=

=

Find this function, without
the x, in the table of
generating functions.

=

=

Note that

=

=

Thus

=

=

Let m = k + 1,
so k = m - 1.

=

Since the m = 0
term is 0, we get:

=

Thus

=

Since the series
must be unique,
we conclude:

=

=