Mathematics for Computer Science

Chapter 15 Generating Functions646

In the ring of formal power series, equation (15.20) implies that the zero se-

quenceZhas no inverse, so1=Zis undefined—just as the expression 1/0 is unde-

fined over the real numbers or the ringZnof Section 8.7.1. It’s not hard to verify

that a series has an inverse iff its initial element is nonzero (see Problem 15.26).

Now we can explain the proper way to understand a generating function defini-

tion

G.x/WWD

X^1

nD 0

gnxn:

It simply means thatG.x/really refers to its infinite sequence of coefficients.g 0 ;g 1 ;:::/

in the ring of formal power series. The simple expression,x, can be understood as

referring to the sequence

XWWD.0;1;0;0;:::;0;:::/:

Likewise, 1 xabbreviates the sequenceJabove, and the familiar equation

1

1 x

D 1 CxCx^2 Cx^3 C


 (15.21)

can be understood as a way of restating the assertion thatKis1=J. In other words,

the powers of the variablexjust serve as a place holders—and as reminders of the

definition of convolution. The equation (15.21) has nothing to do with the values

ofxor the convergence of the series. Rather, it is stating a property that holds in

the ring of formal power series. The reasoning about the divergent series in the

previous section is completely justified as properties of formal power series.

15.6 References

[46], [22], [8] [17]

Problems for Section 15.1

Practice Problems

Problem 15.1.

The notationŒxnçF.x/refers to the coefficient ofxnin the generating function

F.x/. Indicate all the expressions below that equalŒxnç4xG.x/(most of them do).

4ŒxnçxG.x/ 4xŒxnçG.x/ Œxn^1 ç4G.x/

.Œxnç4x/
ŒxnçG.x/ .Œxç4x/
ŒxnçxG.x/ ŒxnC^1 ç4x^2 G.x/