Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 67

Difference Equation

Numeric Function

Generating Function

Fig. 3.1 Procedure to solve LRRCC (Alternate Method).

Let LRRCC be of equation (3.4), i.e.,

A 0 an + A 1 an–1 + A 2 an–2 + ...... + Ak an–k = f(n)

(for n – k ≥ 0orn ≥ k because n – k should not be negative)

Multiplying equation (3.4) by zn and summing for k ≤ n ≤ ∞.

Thus, we have

nk

zn

=

∞

∑ (A 0 an + A 1 an–1 + A 2 an–2 + ...... + Ak an–k) =

nk

fn

=

∞

∑ ()

or

nk=

∞

∑[A 0 (anz

n) + A

1 (an–1z

n) + A

2 (an–2z

n) + ...... + A

k (an–k^ z

n)) =

nk=

∞

∑ f(n)zn ;

We know that, the numeric function a = (a 0 , a 1 , a 2 , ...... an , ......) can be expressed by

the generating function A(z),where

A(z) = a 0 + a 1 z + a 2 z^2 + ...... + anzn + ....... ;

or anzn = A(z) – a 0 – a 1 z – a 2 z^2 + ...... ak–1zk–1 ;

Thus,

nk=

∞

∑ A 0 (anzn) = A 0 [A(z) – a 0 – a 1 z – a 2 z^2 + ...... – ak–1zk–1] ;

similarly

nk=

∞

∑A 1 (an–1zn) = A 1 z [A(z) – a 0 – a 1 z – a 2 z^2 + ......– ak–2zk–2] ;

and so on..... ..... .....

nk=

∞

∑Ak(an–kzn) = Akzk[A(z) – a 0 – a 1 z – a 2 z^2 +......– an–k–1zn–k–1] ;

Add and solve above equations for A(z), so we obtain

A(z) = 1/(A 0 + A 1 z +......+Akzk) [

nk=

∞

∑ f(n)zn + A 0 (a 0 + a 1 z + ...... + ak–1zk–1)

+ A 1 z(a 0 + a 1 z + ......+ ak–2zk–2) + A 2 z^2 (a 0 + a 1 z + ......+ ak–2zk–2) +......

+ Akzk(a 0 + a 1 z + ......+ an–k–1zn–k–1)] ;

(3.23)

Example 3.6. Solve the difference equation an + 5 an–1 + 6 an–2 = 5 given in example 4.4 (b) for
n ≥ 2 (using alternate method) and base conditions a 0 = 1 and a 1 = 2.
Sol. We first determine the generating function A(z) for the difference equation. Since differ-
ence equation is valid for n ≥ 2, so multiply the difference equation to zn and take sum from n
= 2 to ∞. Thus we obtain,