文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-Tzu Juan
Chapter 10 Recurrence Relation
§ The Method of Generating
Functions
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-Tzu Juan 1
§ The Method of Generating Functions
Ex : an 3an1 = n, n 1
a0 = 1
Sol. (1/2)
1 1 1
(n = 1) a1x 3a0x = 1x
2 2 2
(n = 2) a2x 3a1x = 2x
+) : :

n n n
anx 3an1x =nx ……(1)
n 1 n 1 n 1

Let f(x) = a xn be the generating function for the sequence a , a , a , …
n 0 n  0 1 2
then (1) (f(x) a ) 3xf(x) =nxn
0 n 0
(f(x) 1) 3xf(x) = x/(1 x)2 (By p-420 Ex (e))
1 x
 f(x) = 
13x (13x)(1x)2
(c) Spring 2007, Justie Su-Tzu Juan 2
§ The Method of Generating Functions
Ex : an 3an1 = n, n 1
a0 = 1
Sol. (2/2)
x A B C
Let 
(13x)(1x)2 1x (1 x)2 13x
 x = A(1 x)(1 3x) + B(1 3x) + C(1 x)2
when x = 1: 1 = B(2)  B = 1/2
when x = (1/3): (1/3) = C(2/3)2  C = 3/4
when x = 0: 0 = A + B + C  A = 1/4
1 1 1 3 7 1 1
∴ f (x)  4  2  4  4  4  2
13x 1x (1x)2 13x 13x 1x (1x)2
n n 2 n
∴ an = (7/4)3 (1/4)1 (1/2)( n)(1)
= (7/4)3n (1/4) (1/2)(n + 1)
n
∴ an = (7/4)3 (1/2)n (3/4), n 0
(test another method that mention in section )
(c) Spring 2007, Justie Su-Tzu Juan 3
§ The Method of Generating Functions
Ex : an+2 5an+1 + 6an = 2, n 0
a0 = 3; a1 = 7
Sol. (1/2)
n+2 n+2 n+2 n+2
 an+2x 5an+1x + 6anx = 2x

n+2 n+2 n+2 n+2
an+2x 5an+1x +6 anx = 2x
n 0 n0 n0 n0

n+2 n+1 2 n 2 n
an+2x 5x an+1x + 6x anx = 2x x
n 0  n0 n0 n0
n
 Let f(x) = anx be the generating function for the solution,
n 0
2 2
then by : (f(x) a0 a1x) 5x(f(x) a0) + 6x f(x) = 2x /(1 x)
(f(x) 3 7x) 5x(f(x) 3) + 6x2f