Mathematics for Computer Science

Chapter 15 Generating Functions656

so
H.x/WWD
x
.1x/^2

D 0 C1xC2x^2 C3x^3 C

is the generating function for the sequence of nonnegative integers. Therefore

1 Cx

.1x/^3

DH^0 .x/D 1 C 22 xC 32 x^2 C 42 x^3 C


;

so
x^2 Cx
.1x/^3
DxH^0 .x/D 0 C1xC 22 x^2 C 32 x^3 C


Cn^2 xnC

is the generating function for the nonnegative integer squares.

(a)Prove that for allk 2 N, the generating function for the nonnegative integer
kth powers is a quotient of polynomials inx. That is, for allk 2 Nthere are
polynomialsRk.x/andSk.x/such that

Œxnç



Rk.x/

Sk.x/



Dnk: (15.23)

Hint:Observe that the derivative of a quotient of polynomials is also a quotient of
polynomials. It is not necessary work out explicit formulas forRkandSkto prove
this part.

(b)Conclude that iff.n/is a function on the nonnegative integers defined recur-
sively in the form

f.n/Daf.n1/Cbf.n2/Ccf.n3/Cp.n/ ̨n

where thea;b;c; ̨ 2 Candpis a polynomial with complex coefficients, then
the generating function for the sequencef.0/;f.1/;f.2/;:::will be a quotient of
polynomials inx, and hence there is a closed form expression forf.n/.

Hint:Consider
Rk. ̨x/
Sk. ̨x/

Problem 15.18.
The method of partial fractions can only be applied to rational functions—that is,
quotients of polynomials—and there are many interesting generating functions that
are not of this form. Catalan numbers come up frequently in counting the sizes