Generating Function
Generating function
Representation of an infinite sequence of
numbers as the coefficients of a formal
power series
Formal Definition
Examples
Cont…
1, 2, 3, 4, 5, …
G(x) = 1+2x+3x2+4x3+5x4…
0, 1, 2, 3, 4, …
G(x) = 0 + x + 2x2 + 3x3 + 4x4 + 5x5…
1, – 1, 1, – 1, …
G(x) = 1 – x + x2 – x3 + x4 – x5…
1, a, a2, a3, …
G(x) = 1 + ax + a2x2 + a3x3 + a4x4…
1, – a, a2, – a3, …
G(x) = 1 – ax + a2x2 – a3x3 + a4x4, …
Closed Form of Generating Function
1, 1, 1, 1, 1, …
G(x) = 1+x+x2+x3+x4…
= 1/1-x
ak = 1
G(x) = 1+x+x2+x3+x4…
= 1/1-x
2, 2, 2, 2, 2, …
G(x) =
2+2x+2x2+2x3+2x4…
=
a2(1+x+x
k = 2
2
+x3+x4… )
2, 2,=2,2/1-x
2, 2, …
G(x) =
2+2x+2x2+2x3+2x4
Cont…
1, 2, 3, 4, 5, …
ak = k+1
Generating Function
G(x) = 1 + 2x + 3x2 + 4x3 + 5x4…
Multiply by x
xG(x) = x + 2x2 + 3x3 + 4x4…
G(x) – x G(x) = 1+x+x2+x3+…
G(x)(1-x) = 1/1-x
G(x) = 1/(1-x)2
Cont…
1, -1, 1, -1, 1, …
ak = (–1)k
Generating Function
G(x) = 1 – x + x2 – x3 + x4…
= 1 + (-1x) + (-1x)2 + (-1x)3 + (-1x)4…
= 1/(1+x)
0, 1, 2, 3, 4, 5, …
ak = k
Generating Function
G(x) = 0 + x + 2x2 + 3x3 + 4x4…
= x + 2x2 + 3x3 + 4x4…
= x(1 + 2x + 3x2 + 4x3…)
G(x) = x/(1-x)2
Cont…
0, 0, 1, 1, …
Generating Function
G(x) = 0 + 0x + 1x2 + 1x3 + 1x4…
= x2 + x3 + x4 …
= x2(1 + x + x2 + x3 + x4…)
G(x) = x2/(1-x)
1, 1, 0, 1, 1, …
Generating Function
G(x) = 1 + 1x + 0x2 + 1x3 + 1x4…
= 1 + x + x 3 + x4 …
= (1 + x + x2 + x3 + x4…) – x2
= 1/(1–x) – x2
Cont…
1, 0, -1, 0, 1, 0, -1, 0, …
Generating Function
G(x) = 1 + 0x + (-1)x2 + 0x3 + (1)x4 +…
= 1 – x 2 + x4 – x6 + …
= 1 + (–x2) + (–x2)2 + (–x2)3 +…
= 1/(1– (–x2))
= 1/(1+x2)
3, –3, 3, –3, 3, –3, …
Generating Function
G(x) = 3/(1+x)
Cont…
8C0, 8C1, 8C2, 8C3, … 8C8 , 0, 0, 0…
Generating Function
G(x) = 8C0 + 8C1 + 8C2 + 8C3 +…+ 8C8 + 0 + 0
+…
= 8C0+8C1x+8C2x2+…+8C8x8+0x9+0x10+
…ak = 2 + 3k
= (1+x)
Generating Function
8
G(x) = 2/(1 – x) + 3x/(1 – x)2
a k = 4k
Generating Function
G(x) = 1 + 4x + 42x2 + 43x3 + 44x4 + …
= 1/(1 – r)
= 1/(1 – 4x)
Cont…
ak = (-2)k
Generating Function
G(x) = 1 – 2x + 22x2 – 23x3 + 24x4 + …
= 1/(1 – r)
= 1/(1 – (–2)x)
= 1/(1 + 2x)
Common Generating
Function
ak G(x)
----------------------------------------------
1 1/(1-x)
(-1)k 1/(1+x)
c c/(1-x)
k+1 1/(1-x)2
k x/(1-x)2
ak 1/(1-ax)
(-a)k 1/(1+ax)
k2 x(1+x)/(1-x)3
kak ax/(1–ax)2
Exercise
Find the closed form of following generating
functions:
a = 3
k
G(x)= 3/(1-x)
ak = k+3
G(x) = x/(1-x)2 + 3/(1-x)
a k = 3k
G(x) = 1/(1-3x)
ak = k(2+3k)
G(x) = 2x/(1-x)2 + 3x(1+x)/(1-x)3
ak = k(k-1)
3 2
Cont…
Find the closed form of following generating
functions:
0, 0, 0, 1, 1, 1, …
G(x) = 0 + 0x + 0x2 + 1x3 + 1x4 + 1x5 + 1x6 + …
= x3 + x4 + x5 + x6 + …
= x3 (1 + x2 + x3 + x4 + …)
= x3 (1/(1-x))
= x3 /(1-x)
0, 0, 1, 2, 3, 4, …
G(x) = 0 + 0x + 1x2 + 2x3 + 3x4 + 4x5 + …
= x2 + 2x3 + 3x4 + 4x5 + …
= x2 (1 + 2x + 3x2 + 4x3 + …)
= x2 (1/(1-x)2)
= x2/(1-x)2
Cont…
3, 9, 27, 81, …
G(x) = 3 + 9x + 27x2 + 81x3 + …
= 3(1 + 3x + 9x2 + 27x3 + …)
= 3(1 + 3x + 32x2 + 33x3 + …)
= 3 (1/(1-3x))
= 3/(1-3x)
1, -2, 3, -4, …
G(x) = 1 + 2(-x) + 3(-x)2 + 4(-x)3 + …
= 1 + 2(-x) + 3(-x)2 + 4(-x)3 + …
= 1/(1+x)2
Solve Recurrence Relation with
Generating Function
Steps
Multiply by xr in the given equation
Take summation from r = k to ∞, if k initial
conditions are given
Write each summation in the form of G(x) or
closed form
Substitute the value of each summation and find
G(x)
Find partial fractions of G(x)
Write ar
G(x) = a0 + a1x + a2x2 + a3x3 + …
Cont…
Solve the equation ar – 2ar-1 – 3ar-2 = 0, a0 = 3, a1 = 1
using generating functions.
Solution:
ar – 2ar-1 – 3ar-2 = 0
ar xr – 2ar-1xr – 3ar-2xr = 0
= a2x2 + a3x3 + a4x4 +…
G(x) = a0 + a1x + a2x2 + a3x3 + …
= G(x) – a0 – a1x
Cont…
= a1x2 + a2x3 + a3x4 + …
= x(a1x + a2x2 + a3x3 + …)
= x(G(x) – a0)
= a0x2 + a1x3 + a2x4 + …
= x2(a0 + a1x + a2x2 + …)
= x2 G(x)
G(x) – a0 – a1x x(G(x) – a0) 3x2 G(x) = 0
(1 2x 3x2) G(x) = a0 + a1x 2xa0
Substitute value of a0 and a1
(1 2x 3x2) G(x) = 3 + x 6x
(1 2x 3x2) G(x) = 3 5x
Cont…
G(x) = 3 5x / (1 2x 3x2)
= 3 5x / (3x2 2x 1)
= 3 5x / (x+1) (3x 1)
= 5x 3/ (x+1) (3x 1)
Find partial fraction
G(x) = 2/(x+1) 1/(3x 1)
= 2/(1+x) 1/(1 3x)
ar = 2(-1)r + 3r
Cont…
Solve the equation ar – ar-1 – 2ar-2 = 0, where a0 = 0, a1
= 1 using generating functions.
Solution:
ar – ar-1 – 2ar-2 = 0
ar xr – ar-1xr – 2ar-2xr = 0
= a2x2 + a3x3 + a4x4 +…
G(x) = a0 + a1x + a2x2 + a3x3 + …
= G(x) – a0 – a1x
Cont…
= a1x2 + a2x3 + a3x4 + …
= x(a1x + a2x2 + a3x3 + …)
= x(G(x) – a0)
= a0x2 + a1x3 + a2x4 + …
= x2(a0 + a1x + a2x2 + …)
= x2 G(x)
G(x) – a0 – a1x x(G(x) – a0) 2x2 G(x) = 0
(1 x 2x2) G(x) = a0 + a1x 2xa0
Put value of a0 and a1
(1 x 2x2) G(x) = x
G(x) = x / (1 x 2x2)
Cont…
G(x) = x / (1 x 2x2)
= x / (2x2 x 1)
= x / (2x2 2x – x 1)
= x / 2x(x + 1) – 1 (x + 1)
= x / (2x – 1)(x + 1)
= x / (1 – 2x)(x + 1)
Find partial fraction
G(x) = 1/3(1 – 2x) + –1/3(1 + x)
ar = 1/3 . 2r + –1/3 . (– 1r)
Cont…
Solve the equation ar = 3ar-1 + 2, where a0 = 1 using
generating functions.
Solution:
ar = 3ar-1 + 2
ar xr = 3ar-1xr + 2xr
= a1x1 + a2x2 + a3x3 + a4x4 +…
= G(x) – a0
= G(x) – 1
Cont…
= a0x + a1x2 + a2x3 + a3x4 + …
= x(a0 + a1x + a2x2 + a3x3 + …)
= x G(x)
= x + x2 + x3 + x4 + …
= x(1 + x + x2 + x3 + x4 + …)
= x/(1-x)
G(x) – 1 3 xG(x) + 2x/(1 – x)
G(x) – 3 xG(x) = 1 + 2x/(1 – x)
G(x) (1 – 3x) = (1 + x)/(1 – x)
G(x) = (1 + x)/(1 – x)(1 – 3x)
Cont…
G(x) = (1 + x)/(1 – x)(1 – 3x)
Find partial fraction
G(x) = –1/(1 – x) + 2/(1 – 3x)
G(x) = –1/(1 – x) + 2/(1 – 3x)
ar = – 1 + 2.3r
Cont…
Solve the equation ar+2 – 2ar+1 + ar = 2r where a0 = 2
and a1 = 1 using generating functions.
Solution:
ar+2 – 2ar+1 + ar = 2r
ar+2 xr – 2ar+1 xr + ar xr = 2r xr
= a2 + a3x + a4x2 +…
= 1/x2(a2 x2 + a3x3 + a4x4 +…)
= 1/x2(G(x) – a0 – a1 x)
= 1/x2(G(x) – 2 – x)
Cont…
= a1 + a2x + a3x2 + …
= 1/x (a1 x+ a2x2 + a3x3 + …)
= 1/x (G(x) – a0)
= 1/x (G(x) – 2)
= a0 + a1x + a2x2 + a3x2 + …
= G(x)
= 1 + 2x + 22x2 + 23x3 + …
= 1/(1 – 2x)
=
1/x2(G(x) – 2 – x) 2/x (G(x) – 2) G(x) = 1/(1 – 2x)
Cont…
1/x2(G(x) – 2 – x) 2/x (G(x) – 2) G(x) = 1/(1 – 2x)
G(x) – 2 – x – 2x (G(x) – 2) G(x)x2 = x2 /(1 – 2x)
G(x)(1 – 2 + x2) =2 – 3x + x2/(1 – 2x)
G(x)(1 – x)2 =2 – 3x + x2/(1 – 2x)
G(x) = 2/(1 – x)2 – 3x/(1 – x)2 + x2/(1 – 2x) (1 – x)2
Find partial fraction of x2/(1 – 2x) (1 – x)2
x2/(1 – 2x) (1 – x)2 = 1/(1 – 2x) – 1/(1 – x)2
G(x) = 2/(1 – x)2 – 3x/(1 – x)2 + 1/(1 – 2x) – 1/(1 – x)2
= 1/(1 – x)2 – 3x/(1 – x)2 + 1/(1 – 2x)
ar = (r + 1) – 3r + 2r
