Mathematical Foundation of Computer Science

DHARM

60 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

2. if, kth order LRRCC has fewer than k values of numeric function then numeric func-
   tion does not return unique solution. For example, the recurrence relation,
   an + an–1 + an–2 = 4 (3.6)
   and base condition a 0 = 2, then we can determine many numeric functions (shown below) that
   will satisfy both the recurrence relation and the base condition.
   2, 0, 2, 2, 0, 2, 2, 0,......
   2, 2, 0, 2, 2, 0, 2, 2,......
   2, 5, – 3, 2, 5, – 3, 2,......


3. More than k values of numeric functions might be impossible for the existence of a
   numeric function that satisfies the recurrence relation and the given base condition/s. For
   example, the recurrence relation in (3.6), if we have the base conditions a 0 = 2, a 1 = 2 and a 2 = 2
   then a 0 , a 1 and a 2 doesn’t satisfy the recurrence relation simultaneously. Therefore, no numeric
   function simultaneously satisfies the recurrence relation and the base condition both.

3.3 Finding the Solution of LRRCC........................................................................................

The discrete numeric function which is the solution of a linear difference equation is the sum

of two discrete numeric functions–the homogeneous solution and the particular solution. Con-

sider the linear recurrence relation with constant coefficients (LRRCC) equation (3.4)

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

Then, the solution a(h) = (a0(h), a1(h), a2(h), ......, an(h), ...) that satisfies the difference equa-

tion (3.7) is called homogeneous solution where subscript h denotes the homogenous solution

values.

A 0 an(h) + A 1 an–1(h) + A 2 an–2(h) + ......+ Ak an–k(h) = 0 ; (3.7)

Simultaneously, a solution a(p) = (a0(p), a1(p), a2(p),......, an(p), ...) that satisfies the equation,

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

is called particular solution where subscript p denotes the particular solution values.

Thus we have,

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

(3.9)

Clearly, the difference equation (3.4) has the complete solution a = a(h) + a(p) which is

the summation of the homogeneous solution and the particular solution.

3.3.1 Method of Finding Homogenous Solution..........................................................

Let A 0 an + A 1 an–1 + A 2 an–2 + ......+ Ak an–k = 0 ; (3.10)
is the homogenous equation,

Step 1
Find the characteristic equation for the above recurrence relation. Therefore substitute
Aαn for an in equation (3.10). Thus we have
A 0 (Aαn )+ A 1 (Aαn–1 ) + A 2 (Aαn–2) + ......+ Ak (Aαn–k) = 0 ;
or A 0 αn + A 1 αn–1 + A 2 αn–2 + ......+ Ak αn–k = 0 ;
After simplification we obtain the equation
A 0 αk + A 1 αk–1 + A 2 αk–2 + ......+ Ak = 0 ; (3.11)