DHARM
46 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
and assume the scale of relation is 1 – pz – qz^2. So we have
an – p an–1 – q an–2 = 0
Assume, A(z) = a 0 + a 1 z + a 2 z^2 + ........ ........ + an–1 zn–1
- pz.A(z) = – pa 0 z – pa 1 z^2 – ................. – pan–2 zn–1 – p an–1 zn
- qz^2 .A(z) = – qa 0 z^2 – ................. – qan–3 zn–1 – q an–2 zn – qan–1 zn+1
(1 – pz – qz^2 ) A(z) = a 0 + (a 1 – pa 0 ) z + ............. – (pan–1 + qan–2) zn – qan– 1 .zn+^1
For the coefficient of every other power of z is zero in consequence of the relation
an – p an–1 – q an–2 = 0
i.e., A(z) = [a 0 + (a 1 – pa 0 ) z]/(1 – pz – qz^2 )
- [(pan–1 + qan–2) zn – qan–1 zn+1]/(1 – pz – qz^2 ) (2.6)
For large value of n series (2.5) is infinite and so second fraction of the equation (2.6)
decreases indefinitely. Thus we have the sum
A(z) = [a 0 + (a 1 – pa 0 ) z]/(1 – pz – qz^2 ) (2.7)
If we develop this fraction in ascending powers of z, we shall obtain as many terms of
the original series as we please. Therefore, the expression (2.7) is called generating function
of the infinite series (2.5).
As we mention in the previous section that for a numeric function an we uses a 0 , a 1 , a 2 ,
..., an, .....to denote its values at 0, 1, 2, ......, n, ...... Here we introduce an alternative way to
represent numeric functions, such as for a numeric function (a 0 , a 1 , a 2 , ..., an, .....) we define an
infinite series,
a 0 + a 1 z + a 2 z^2 + ........ + an zn + ............
Here z is a formal variable and powers of z is used as generator in the infinite series
such that the coefficient of zn returns the value of the numeric function at n. For a numeric
function an we write A(z) to denote its generating function and so the above infinite series can
be written in closed form as shown in equation (2.7), i.e.,
A(z) = [a 0 + (a 1 – pa 0 )z]/(1 – pz – qz^2 )
(where (1 – pz – qz^2 ) is the scale of relation)
For example, the numeric function (5^0 , 5^1 , 5^2 , ..., 5n, .....) we define an infinite series,
50 + 5^1 z + 5^2 z^2 + ........ + 5n zn + ............
Therefore we obtain the summation of infinite series A(z) = 1/(1 – 5z). A(z) is the gener-
ating function that represent the numeric function in a compact way. Hence for a numeric
function we can easily obtain its generating function and vise - versa. In fact an alternate way
to representing numeric function leads to efficiency and easiness in some context that we wish
to carry out.
Consider a numeric function an = 1 for n ≥ 0, then its generating function A(z) =
1/(1 – z). Similarly the generating function of the numeric function bn = kn for n ≥ 0 will be
B(z) = 1/(1 – kz). It is quite often that generating function can be expressed as a group of
equivalent partial fractions and the general term of series may be easily found where the
coefficient of zn represent the corresponding numeric function. Thus, suppose generating
function can be decomposed into partial fractions,
P/(1 – αz) + Q/(1 + βz) + R/(1 – γz)
Then coefficient of the zn in the general term is
{P. αn + (– 1)n B. βn + (n + 1) R. γn} for n ≥ 0
that will be equivalent to numeric function.
