Generating Functions
The generating function f or the sequence a , a , … a , … … of real numbers in infinite series.
G(x) = a + a x + a x + ⋯ + a x + ⋯ = ∑ (k + 1)x … (1)
For example, the generating function for the sequences {a } where a = 2, a = 3 and a = (k + 1) are
∑ 2x , ∑ 3 x and ∑ (k + 1)x respectively.
Some special Generating Functions:
1. The generating function of the sequence 1, 1, 1, ... is
G(x) =1 + x + x + ⋯ = ∑ x
= (1 − x) = ⎯⎯⎯
2. The generating function of the sequence 1, 2, 3, 4, ... is
G(x) = 1 + 2x + 3x + 4x + ⋯ = ∑ (k + 1)x
= (1 − x) = (⎯⎯⎯⎯⎯in
)
closed form |x| < 1.
3. The generating function of the sequence 1, a, a , a , … is
G(x) = 1 + ax + a x + a x + ⋯ = ∑ a x
=(1 − ax) = ⎯⎯⎯⎯in closed form |ax| < 1
4. The generating function of the sequence 0, 1, 2, 3, ... Is
G(x) = 0 + 1x + 2x + 3x + ⋯ = ∑ kx
= x(1 + 2x + 3x + ⋯ )
= x(1 − x) = (⎯⎯⎯⎯⎯in
)
closed form.
Example. Find the generating function for the sequence 𝟏, 𝐚, 𝐚𝟐 , … … . . where 𝐚 is a fixed constant.
Sol. Let G(x) = 1 + ax + a x + a x + ⋯
So G(x) − 1 = ax + a x + a x + ⋯
( )
or ⎯⎯⎯⎯⎯ = 1 + ax + a x + a x + ⋯
( )
or ⎯⎯⎯⎯⎯ = G(x) ⇒ G(x) = ⎯⎯⎯⎯.
The required generating function is ⎯⎯⎯⎯.
CS206 Page 1
S. No. General term of sequence 𝐚𝐤 Generating Function G(x)
1. 1 1
⎯⎯⎯⎯⎯
1−x
2. (−1) 1
⎯⎯⎯⎯⎯
1+x
3. k+1 1
⎯⎯⎯⎯⎯⎯⎯
(1 − x)
4. k x
⎯⎯⎯⎯⎯⎯⎯
(1 − x)
5. k(k + 1) 2x
⎯⎯⎯⎯⎯⎯⎯
(1 − x)
6. (k + 1)(k + 2) 2
⎯⎯⎯⎯⎯⎯⎯
(1 − x)
7. a 1
⎯⎯⎯⎯⎯⎯
1 − ax
8. (−a) 1
⎯⎯⎯⎯⎯⎯
1 − ax
9. ⎯⎯ e
!
Example. Find a closed form for the generating function for each of the following sequence.
(a) 0, 0, 1, 1, 1, ...
(b) 1, 1, 0, 1, 1, 1, 1, 1, ...
(c) 1, 0, -1, 0, 1, 0, -1, 0, 1, ...
(d) C(8,0), C(8,1), C(8,2), ... , C(8,8), 0, 0, ...
(e) 3, -3, 3, -3, 3, -3, ...
Sol.
(c) We know ⎯⎯⎯⎯= (1 + x ) = 1 − x + x − x + x … ∞.
= 1 + 0 x + (−1)x + 0 x + 1 x + 0 x + (−1)x + ⋯
So the generating function of 1, 0, -1, 0, 1, 0, -1, 0, 1, ... is ⎯⎯⎯⎯.
(d) We know (1 + x) = C(8, 0)x + C(8, 1)x + ⋯ + C(8, 8)x + 0 + 0 + ⋯
= ∑ C(8, n)x .
So the generating function of C(8, 0), C(8, 1), ... (C8, 8), 0, 0, ... is (1 + x) .
Example. Find the generating function of the sequence {a } if a = 2 + 3k.
Sol. The generating function of a sequence whose general term is 2 is F(x) = ⎯⎯⎯
The generating function of a sequence whose general term is 3k is G(x) = (⎯⎯⎯⎯⎯
)
.
Hence, the required generating function is F(x) + G(x) = ⎯⎯⎯+ (⎯⎯⎯⎯⎯.
)
CS206 Page 2
Example. Find the coefficient of
𝟑
(a) 𝐱 𝟏𝟎 in 𝟏 + 𝐱 𝟓 + 𝐱 𝟏𝟎 + ⋯
𝟑
(b) 𝐱 𝟏𝟐 in 𝐱 𝟑 + 𝐱 𝟒 + 𝐱 𝟓 + ⋯
𝟓
(c) 𝐱 𝟏𝟖 in 𝐱 + 𝐱 𝟐 + 𝐱 𝟑 + 𝐱 𝟒 + 𝐱 𝟓 𝐱𝟐 + 𝐱𝟑 + 𝐱𝟒 + ⋯
Sol.
(a) We know
(1 + x + x + ⋯ ) = [(1 − x ) ]
= (1 − x ) = ∑ C(3 + r − 1, r)x
Since, we have to find the coefficients of x , 5r = 10 ⇒ r = 2
The required coefficient is C(3 + 2 − 1, 2) = C(4, 2) = 6.
(c) We know (x + x + x + x + x )(x + x + x + ⋯ )
= x(1 + x + x + x + x )x (1 + x + x + ⋯ )
= x (1 − x )(1 − x) (1 − x)
= (x − x )(1 − x)
= (x −x ) C(6 + r − 1, r)x
Hence, the coefficient of x is C(6 + 7 − 1, 7) − C(6 + 2 − 1, 2) = C(12, 7) − C(7, 2).
CS206 Page 3
