DHARM

48 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

• If bn = knan, where k is any arbitrary constant then corresponding generating func-
  tion is B(z) = A(kz) = 1/(1 – kz). Since numeric function bn is expressed in infinite
  series as
  a 0 + k.a 1 z + k^2 a 2 z^2 + ................... + kn anzn + ......
  = a 0 + a 1 (kz) + a 2 (kz)^2 + ................... + an (kz)n + ......
  Therefore, generating function B(z) = A(kz) = 1/(1 – kz).


• Since A(z) is the generating function of function an so generating function of SI an will
  be zI A(z), for any positive integer I. For example, let generating function B(z) =
  z^8 /(1 – 3z) then it can be written as,
  B(z) = z^8. 1/(1 – 3z) ≡ zI A(z)
  Then its corresponding numeric function will be S^8 an where an is the numeric func-
  tion for the function 1/(1 – 3z) that is equal to 3n.
  Therefore, we obtain numeric function S^8 3 n, i.e.,

S

for 0

for

8

(^38)
07
38
n
n
n
n

≤≤
≥
R
S
T
−

• Likewise, generating function for the numeric function S–I an for any integer I, will
  be
  z–I [A(z) – a 0 – a 1 z – a 2 z^2 – ........ – aI–1 zI–1]
  Since A(z) = a 0 + a 1 z + a 2 z^2 + ........ + aI–1 zI–1 + aI zI ....... + an zn + ....
  or, A(z) – a 0 – a 1 z – a 2 z^2 – ........ – aI–1 zI–1 = aI zI + aI+1 zI+1 + ..... + an zn + ....
  Multiplied both side by z–I, hence we obtain
  z–I [A(z) – a 0 – a 1 z – a 2 z^2 – ........ – aI–1 zI–1] = aI + aI+1 z + ..... + an zn–I + ....
  = an+I zn for n ≥ 0
  That is equivalent to S–I an.
  For example, let an = 3n+5 for n ≥ 0 which is equivalent to numeric function S–5.3n and its
  corresponding generating function can be computed by using the expression,
  A(z) = z–I [A(z) – a 0 – a 1 z – a 2 z^2 – ........ – aI–1 zI–1]
  i.e., A(z) = z–5 [1/(1 – 3z) – 3^0 – 3^1 z – 3^2 z^2 – 3^3 z^3 – 3^4 z^4 ]
  = z–5 [3^5 .z^5 /(1 – 3z)] = 3^5 /(1 – 3z).
  Example 2.30 Find the generating function for the numeric function an such that

a

0 for 0 n 5

1forn6

2forn7

3forn8

4forn9

0 for n 10

n=

≤≤

=

=

=

=

≥

R

S

|

||

T

|

|

|

Sol. Let A(z) is the generating function for an where,

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

Since values of a 0 to a 5 and a 10 onwards are equal to zero. So

A(z) = a 6 z^6 + a 7 z^7 + a 8 z^8 + a 9 z^9 + a 10 z^10

= 1.z^6 + 2.z^7 + 3.z^8 + 4.z^9 + 0.z^10

= z^6 .(1 + 2z + 3z^2 + 4z^3 )