Mathematics for Computer Science

Chapter 15 Generating Functions644

To prove this identity, note that from (15.16), we have

ŒxnçH.x/WWDn
nŠD.nC1/ŠnŠDŒxnç



F.x/ 1

x



ŒxnçF.x/:

In other words,

H.x/D

F.x/ 1

x

F.x/; (15.18)

Solving (15.18) forF.x/, we get

F.x/D

xH.x/C 1

1 x

: (15.19)

ButŒxnç.xH.x/C1/is.n1/
.n1/Šforn 1 and is 1 fornD 0 , so by the
convolution formula,

Œxnç



xH.x/C 1

1 x



D 1 C

Xn

iD 1

.i1/
.i1/Š:

The identity (15.17) now follows immediately from (15.19).

15.5.2 The Ring of Power Series

So why don’t we have to worry about series whose radius of convergence is zero,
and how do we justify the kind of manipulation in the previous section to derive
the formula (15.19)? The answer comes from thinking abstractly about infinite
sequences of numbers and operations that can be performed on them.
For example, one basic operation combining two infinite sequences is adding
them coordinatewise. That is, if we let

GWWD.g 0 ;g 1 ;g 2 ;:::/;

HWWD.h 0 ;h 1 ;h 2 ;:::/;

then we can define the sequence sum, ̊, by the rule:

G ̊HWWD.g 0 ChC0;g 1 Ch 1 ;:::;gnChn;:::/:

Another basic operation is sequence multiplication, ̋, defined by the convolution
rule (notcoordinatewise):

G ̋HWWD

g 0 Ch 0 ;g 0 h 1 Cg 1 h 0 ;:::;

Xn

iD 0

gihni;:::

!

: