Matematicas Discretas, Chen

DISCRETE MATHEMATICS
W W L CHEN
c
W W L Chen, 1992, 2008.

This chapter is available free to all individuals, on the understanding that it is not to be used for financial gain, and may be downloaded and/or photocopied, with or without permission from the author. However, this document may not be kept on any information storage and retrieval system without permission from the author, unlesssuch system is not accessible to any individuals other than its owners.

Chapter 14
GENERATING FUNCTIONS

14.1. Introduction Definition. By the generating function of a sequence a0 , a1 , a2 , a3 , . . . , we mean the formal power series
∞

a0 + a1 X + a2 X + a3 X + . . . =
n=0

2

3

an X n .

Example 14.1.1. The generating function of the sequence k k k , ,..., , 0, 0, 0, 0, . . .0 1 k is given by k k k + X + ... + Xk. 0 1 k This is equal to (1 + X)k by the Binomial theorem. Example 14.1.2. The generating function of the sequence 1, . . . , 1, 0, 0, 0, 0, . . .
k

is given by 1 + X + X 2 + X 3 + . . . + X k−1 =
Chapter 14 : Generating Functions

1 − Xk . 1−X
page 1 of 6

Discrete Mathematics

c

W W L Chen, 1992, 2008

Example 14.1.3. The generatingfunction of the sequence 1, 1, 1, 1, . . . is given by
∞

1 + X + X2 + X3 + . . . =
n=0

Xn =

1 . 1−X

Example 14.1.4. The generating function of the sequence 2, 4, 1, 1, 1, 1, . . . is given by 2 + 4X + X 2 + X 3 + X 4 + X 5 . . . = (1 + 3X) + (1 + X + X 2 + X 3 + . . .)
∞

= (1 + 3X) +
n=0

X n = 1 + 3X +

1 . 1−X

14.2. Some Simple Observations The idea used in the Example 14.1.4can be generalized as follows. PROPOSITION 14A. Suppose that the sequences a0 , a1 , a2 , a3 , . . . and b0 , b1 , b2 , b3 , . . .

have generating functions f (X) and g(X) respectively. Then the generating function of the sequence a0 + b0 , a1 + b1 , a2 + b2 , a3 + b3 , . . . is given by f (X) + g(X). Example 14.2.1. The generating function of the sequence 3, 1, 3, 1, 3, 1, . . . can beobtained by combining the generating functions of the two sequences 1, 1, 1, 1, 1, 1, . . . and 2, 0, 2, 0, 2, 0, . . . . Now the generating function of the sequence 2, 0, 2, 0, 2, 0, . . . is given by 2 + 2X 2 + 2X 4 + . . . = 2(1 + X 2 + X 4 + . . .) = 2 . 1 − X2

It follows that the generating function of the sequence 3, 1, 3, 1, 3, 1, . . . is given by 1 2 + . 1−X 1 − X2

Sometimes,differentiation and integration of formal power series can be used to obtain the generating functions of various sequences. Example 14.2.2. The generating function of the sequence 1, 2, 3, 4, . . . is given by 1 + 2X + 3X 2 + 4X 3 + . . . = d (X + X 2 + X 3 + X 4 + . . .) dX d d 1 1 = (1 + X + X 2 + X 3 + X 4 + . . .) = = . dX dX 1 − X (1 − X)2
page 2 of 6

Chapter 14 : Generating Functions

DiscreteMathematics

c

W W L Chen, 1992, 2008

Example 14.2.3. The generating function of the sequence 1 1 1 0, 1, , , , . . . 2 3 4 is given by X+ X2 X3 X4 + + + ... = 2 3 4 (1 + X + X 2 + X 3 + . . .) dX = 1 1−X dX = C − log(1 − X),

where C is an absolute constant. The special case X = 0 gives C = 0, so that X+ X2 X3 X4 + + − . . . = − log(1 − X). 2 3 4

Another simple observation is thefollowing. PROPOSITION 14B. Suppose that the sequence a0 , a1 , a2 , a3 , . . . has generating function f (X). Then for every k ∈ N, the generating function of the (delayed) sequence 0, . . . , 0, a0 , a1 , a2 , a3 , . . .
k

(1)

is given by X k f (X). Proof. Note that the generating function of the sequence (1) is given by a0 X k + a1 X k+1 + a2 X K+2 + a3 X K+3 + . . . = X k (a0 + a1 X + a2 X 2 +a3 X 3 + . . .) as required. Example 14.2.4. The generating function of the sequence 0, 1, 2, 3, 4, . . . is given by X/(1 − X)2 , and the generating function of the sequence 0, 0, 0, 0, 0, 1, 2, 3, 4, . . . is given by X 5 /(1 − X)2 . On the other hand, the generating function of the sequence 0, 0, 0, 0, 0, 0, 0, 3, 1, 3, 1, 3, 1, . . . is given by 2X 7 X7 + . 1−X 1 − X2 Example 14.2.5....