Mathematical Foundation of Computer Science

DHARM

66 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

In general

j

k

nj

j

k

i

k

i

a j j

=

−

=

−

=

∑∑∑=+

0

1

0

1

0

CPα 1 () (3.21)

Thus, equation (3.21) yields the coefficients Ci’s (for i = 1 to k).
Example 3.5. Solve the difference equation an – 5 an–1 + 6 an–2 = 3n + n for base conditions a 0 = 0
and a 1 = 1.
Sol. For the homogenous solution an(h), the characteristic equation is
α^2 – 5α + 6 = 0 ;
So, characteristic roots are 2 and 3.
Thus an(h) = C 1 .2n + C 2 .3n ;
Find out the particular solution an(p)(see example 3.4 (i)) that is,
an(p) = (– 3).n.3n + (1/3).n + 7/9;
Therefore, the complete solution is,
an = an(h) + an(p)
an = C 1 .2n + C 2 .3n + (– 3).n.3n + (1/3).n + 7/9 ; (3.22)
using base conditions we have the linear equations
C 1 + C 2 = – 7/9 and 2C 1 + 3C 2 = 80/9 ;
that yields C 1 = – 101/9 and C 2 = 94/9
Putting these values of C 1 and C 2 in the equation (3.22) we obtain complete solution
an = (– 101/9) 2n + (94/9) 3n – 3n+1 n + (1/3).n + 7/9 ;

FACT

It should be noted that for a kth order LRRCC, uniqueness of the complete solution is depend
on the uniqueness of the homogenous solution. That is, the unique solution obtains after
solving k linear equations using base conditions that consist of k-consecutive values. Conse-
quently, the unknown coefficients can be determined uniquely by the value of the numeric
functions at k-consecutive points.
The non-uniqueness of the homogenous solution occurs under following conditions:

1. If number of linear equations is less than k this condition arises when given base
   conditions are fewer than k.


2. If base conditions are more than k.


3. If k values of base conditions are non-consecutive.


4. If kth order recurrence relation is non-linear.

3.4 ALTERNATE METHOD (Finding Solution of LRRCC by Generating

Function)

In the last section we have seen that, more often we can determine the numeric function from

the generating function conveniently. To find out the solution of LRRCC, previously we solve

the difference equation and then determine the numeric function. An alternate method is

that we firstly determine the generating function for the difference equation and then find

the corresponding numeric function. The procedure is pictorially shown in Fig. 3.1.