DHARM50 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE= 2 .3 ....... (n + 1)/n!
= (n + 1)
Therefore we obtain the numeric function an = n + 1 for n ≥ 0 for it values (1, 2, ..., n ,..)
Example 2.33 Determine the generating function for the numeric function (0^2 ,1^2 , 2^2 , ......., n^2 ,
....).
Sol. Since 1/(1 – z) = 1 + z + z^2 + z^3 ............. + zn + ....
Differentiate both sides w.r.t.z, i.e.,
1/(1 – z)^2 = 1 + 2z + 3z^2 + ............. + nzn–1 + ....
Multiply both sides by z so we obtain
z.1/(1 – z)^2 = 1.z + 2z^2 + 3z^3 + ............. + nzn + ....
Differentiate again w.r.t.z and multiply both sides with z, i.e.,
z. (1 + z)/(1 – z)^3 = 0^2 + 1^2 .z + 2^2 .z^2 + 3^2 .z^3 + .............+ n^2 .zn + ....
Thus, we obtain the generating function z. (1 + z)/(1 – z)^3 for the numeric function (0^2 ,1^2 ,
22 , ......., n^2 , ....).
Conversely, the coefficient of zn in z. (1 + z)/(1 – z)^3 is n^2 †, therefore an = n^2 for n ≥ 0.
Example 2.34 Find generating functions of the following discrete numeric functions
(i) 1, 2/3, 3/9, 4/27, ........(n + 1)/3n, ......
(ii) 0.5^0 , 1.5^1 , 2.5^2 , ........, n.5n, ...........
Sol. (i) Let A(z) is the generating function of the series (1, 2/3, 3/9, 4/27, ........ (n + 1)/3n, ......),
i.e.,
A(z) = 1 + z.2/3 + z^2 .3/9 + z^3 .4/27 + ........ + zn.(n + 1)/3n + .........
or A(z) = 1 + 2.(z/3) + 3.(z/3)^2 + 4.(z/3)^3 + ........+ (n + 1).(z/3)n +......
Since, 1/(1 – z)^2 = 1 + 2z + 3z^2 + ............. + (n + 1)zn + ....
Replace z by z/3 so above equation becomes
1/(1 – z/3)^2 = 1 + 2.(z/3) + 3.(z/3)^2 + ............. + (n + 1).(z/3)n + ....
Therefore, 1/(1 – z/3) is the required generating function.
(ii) Let B(z) is the generating function of the series (0.5^0 , 1.5^1 , 2.5^2 , ........, n.5n, ...........),
i.e.,
B(z) = 0.5^0 + 1.5^1 z + 2.5^2 z^2 + ........ + n.5n zn + ...........
Since, 1/(1 – z) = 1 + z + z^2 + z^3 ............. + zn + .............
Replace z by 5z thus we obtain the equation
1/(1 – 5z) = 1 + 5z + (5z)^2 + (5z)^3 ............. + (5z)n + .............
† Since general term of 1/(1 – z)^3 , is given as
= (– 1)n. zn .(– 3). (– 4). .........(– 3 – n + 1)/n!
Thus, the coefficient of zn in 1/(1 – z)^3 is
= (3). (4). ......... (2 + n)/n!
= (n + 2) (n + 1)/1. 2
Therefore the coefficient of zn in the expansion of z.(1 + z)1/(1 – z)^3 is
= n .(n + 1)/2 + (n – 1) .n/2
= n .2n/2
= n^2