Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 45

| bn | ≤ C | an | for n ≥ C 0

So we have the equality

| 2n | ≤ C. | 3n | for n ≥ C 0

That is true for C = 1 and C 0 = 0, i.e. 2n ≤ 1. 3n for n ≥ 0. Hence an asymptotically

dominates bn. (But its reverse is not true)

(ii) Determine an*bn i.e.,

an*bn = Σ

k

n

= 0

ak bn–k

= Σ

k

n

= 0

3 k 2 n–k

Since, Σ

k

n

= 0

| 2k | ≤ (^) Σ
k
n
= 0
| 3k 2 n–k | for n ≥ 0
So, anbn asymptotically dominates bn.
(iii) Similarly we can show that anbn asymptotically dominates an.

2.4 Generating Functions.......................................................................................................

Before going to start the exact discussion on generating functions let us begin our tour from
the origin of generating functions. Assume a series a 0 + a 1 + a 2 + ........ + an in which, from and
after a certain term is equal to the sum of a fixed number of preceding terms multiplied
respectively by certain constant is called recurring series. For example in the series 1 + 2z + 3z^2

• 4z^3 + 5z^4 + .... , where each term after the second is equal to the sum of the two preceding
  terms multiplied respectively by the constants 2z and – z^2. These quantities being constants
  because they are remain same for all values of n. Thus,
  5 z^4 = (2z). 4z^3 + (– z^2 ). 3z^2
  Therefore we assume that
  a 4 = 2z. a 3 – z^2. a 2
  In general when n is greater then 1, each term is represented by its two immediately
  preceded terms through the equation,
  an = 2z. an–1 – z^2. an–2
  or an – 2z. an–1 + z^2. an–2 = 0 (2.1)
  Equation 2.1 is called scale of relation in which coefficients an, an–1, and an–2 are taken
  with their proper signs. Thus the series 1 + 2z + 3z^2 + 4z^3 + 5z^4 + ...... has scale of relation 1 –
  2 z + z^2. Consequently, if the scale of relation of a recurring series is given, then we could find
  any term of the series, from sufficient number of known preceding terms.
  For example, let 1 – pz – qz^2 – wz^3 (2.2)
  is the scale of relation of the series a 0 + a 1 z + a 2 z^2 + ........ + an zn (2.3)
  Then we have, an zn ≥ pz. an–1 zn–1 + qz^2. an–2 zn–2 + wz^3. an–3 zn–3;
  or an = p. an–1 + q. an–2 + w. an–3; (2.4)
  Thus, any coefficient can be found when coefficients of the three preceding terms are
  known.
  Let us take a series shown in (2.3) and extended up to infinite terms, i.e.,
  a 0 + a 1 z + a 2 z^2 + ........ + an zn + ............ (2.5)