Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 47

Example 2.27 Find the numeric function for the generating function
A(z) = (1 – 8z)/(1 – z – 6z^2 )
Sol. Since A(z) can be expressed in partial fraction i.e.,
A(z) = 2/(1 + 2z) – 1/(1 – 3z)
Then obtain the coefficient of zn in the general term and it will come out to be
(– 1)n 2 n+1 – 3n for n ≥ 0
That is the required numeric function of A(z). Alternatively, we say an = (– 1)n 2 n+1 – 3n
for n ≥ 0.
Example 2.28 Find the generating function and the numeric function for the series
1 + 6 + 24 + 84 + ..............
Sol. The given series is transformed into another infinite series by introducing a formal pa-
rameter z and using power of z as generator in it, i.e.
1 + 6z + 24z^2 + 84z^3 + .............. (2.8)
The scale of relation of the above series is (1 – 5z + 6z^2 ). To explain the method of
determining the scale of relation, let’s assume (1 – pz – qz^2 ) is the scale of relation for the
series (2.8). Therefore to obtain p and q we have the equations,
24 – 6 p – q = 0 and 84 – 24 p – 6q = 0
whence, p = 5, and q = – 6, So the scale of relation is (1 – 5z + 6z^2 ).
Hence, using equation (2.7) we obtain the generating function
A(z) = (1 + z)/(1 – 5z + 6z^2 ).
Since A(z) can be written as,
A(z) = 4/(1 – 3z) – 3/(1 – 2z)
Now obtain the coefficient of zn in the general term of A(z) that will return the numeric
function an i.e.
an = 4.3n – 3.2n for n ≥ 0
Example 2.29 Find numeric function for generating function
A(z) = 2/(1 – 4z^2 )
Sol. Since A(z) can be written as
A(z) = 1/(1 – 2z) + 1/(1 + 2z)
Thus we obtain the numeric function an as,
an = 2n + (– 1)n. 2n for n ≥ 0

or a
n
n n n
=RS
T

0

1

if is odd

2ifis even

Now we shall discuss the common features of generating function corresponding to the

features of numeric functions. Let an, bn, and cn are numeric function and A(z), B(z), and C(z)

are their corresponding generating functions then,

• If cn = an + bn then corresponding generating function C(z) = A(z) + B(z). For example,
  Let an = 2n and bn = 3n for n ≥ 0 then cn = 2n + 3n for n ≥ 0. So C(z) = 1/(1 – 2z) + 1/(1 –
  3 z) = (2 + 3z – 6z^2 )/(1 – 2z).


• If bn = kan, where k is any arbitrary constant then corresponding generating func-
  tion is B(z) = kA(z). For example let an = 5.2n for n ≥ 0 then A(z) = 5/(1 – 2z) is the
  numeric function.