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:

=

=