Mathematics for Computer Science

Chapter 15 Generating Functions628

We’ll use typical generating function reasoning to derive a simple formula for
G.x/. The approach is actually an easy version of the perturbation method of
Section 13.1.2. Specifically,

G.x/D 1 CxCx^2 Cx^3 C


 CxnC




xG.x/D xx^2 x^3 


 xn




G.x/xG.x/D1:

Solving forG.x/gives

1

1 x

DG.x/WWD

X^1

nD 0

xn: (15.3)

In other words,

Œxnç



1

1 x



D 1

Continuing with this approach yields a nice formula for

N.x/WWD 1 C2xC3x^2 C


C.nC1/xnC


: (15.4)

Specifically,

N.x/D 1 C2xC3x^2 C4x^3 C


 C.nC1/xnC




xN.x/D x 2x^2 3x^3 


  nxn 




N.x/xN.x/D 1 Cx Cx^2 C x^3 C


 C xn C




DG.x/:

Solving forN.x/gives

1

.1x/^2

D

G.x/

1 x

DN.x/WWD

X^1

nD 0

.nC1/xn: (15.5)

On other words,

Œxnç



1

.1x/^2



DnC1:

15.1.1 Never Mind Convergence

Equations (15.3) and (15.5) hold numerically only whenjxj< 1, because both
generating function series diverge whenjxj 1. But in the context of generat-
ing functions, we regard infinite series as formal algebraic objects. Equations such
as (15.3) and (15.5) define symbolic identities that hold for purely algebraic rea-
sons. In fact, good use can be made of generating functions determined by infinite
series that don’t convergeanywhere(besidesxD 0 ). We’ll explain this further in
Section 15.5 at the end of this chapter, but for now, take it on faith that you don’t
need to worry about convergence.