Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 49

Note that Generating function to the convolution of numeric functions i.e. cn = an*bn will be

A(z).B(z). Since

cn = an*bn = a 0 bn + a 1 bn–1 + ............... + an–1b 1 + anb 0

which is the coefficient of zn in the product of series

(a 0 + a 1 z + a 2 z^2 + ...... + an zn + ....). (b 0 + b 1 z + b 2 z^2 + ....+ an zn + ....)

And it’s generating function is equal to the product of the generating functions of both

A(z) and B(z), i.e.

C(z) = A(z). B(z)

Example 2.31 Let an = 3n and bn = 5n for n ≥ 0, then determine the generating function for the

convolution of numeric functions an and bn.

Sol. Since generating function corresponding to numeric function an and bn are A(z) = 1/(1 – 3z)

and 1/(1 – 5z) respectively. Let cn = an*bn then its generating function is given by C(z) = A(z).

B(z). Therefore

C(z) = 1/(1 – 3z). 1/(1 – 5z)

Alternatively, C(z) can be written as using partial fraction

C(z) = – 3/2(1 – 3z) + 5/2(1 – 5z)

Therefore its numeric function will be,

cn = – 3/2. 3n + 5/2. 5n or cn = (– 1/2). 3n+1 + (1/2) .5n+1 for n ≥ 0

• If cn = Σ
  I= 0

n

aI then its generating is C(z) = A(z). 1/(1 – z) where A(z) is the generating

function for function aI for I = 0 to n. To prove this fact we recall that if the convolu-

tion of numeric function an and bn is cn, then

cn = IΣ= 0

n

aI. bn–I

And its generating function is given as C(z) = A(z). B(z)

Assume bn–I = 1 then

cn = Σ

I= 0

n
aI. 1
Since generating function for function bn–I = 1 for n ≥ 0 or (1, 1, 1, ........ 1, ....) is B(z) =
1/(1 – z). Therefore,
C(z) = A(z). 1/(1 – z)

where A(z) is the generating function of the numeric function IΣ= 0

n

aI

Example 2.32 Determine the generating function for the numeric function (1, 2, 3, ......., n,

....).

Sol. Since 1/(1 – z) = 1 + z + z^2 + z^3 ............. + zn + zn+1 + ....

Differentiate both side w.r.t.z, i.e.,

1/(1 – z)^2 = 1 + 2z + 3z^2 + ............. + nzn–1 + (n + 1)zn + ....

Thus, we obtain the generating function 1/(1 – z)^2 for the numeric function (1, 2, 3, .....,

n, ...).

Conversely, for generating function 1/(1 – z)^2 , the coefficient of zn (general term) will be,

= (– 1)n (– 2) (– 2 – 1) ........ (– 2 – n + 1)/n!