Example :  Solve for : an = 2 an-1 + 8 an-2 ;  with initial condition  a0 = 4 and a1 = 10

 

Replace  an by rn  ,  an-1 by rn-1        ,  etc ,

 then we the following equation :

                     rn     =    2  rn-1                      +     8 rn-2                 

 

 

when we move all the terms to the left, we get the following :

 

                    rn     -   2  rn-1    -     8 rn-2            = 0

 

which becomes to

 

rn-2     (   r2     -   2  r    -     8 )            =     0

 

as long as  r ≠  0, we must have  ( r2     -   2  r    -     8 )            =     0

 

by solving this quadratic equation (either by quadratic formula or by factorization)

 

   ( r -  4) (r  +  2)  = 0

 

è r = 4 or r = -2

 

So, the general solution for the recurrence relation is

 

   an   =  A*(4) n       +     B (-2)n 

 

then using the initial conditions to determine the coefficient A and B

 

   a0 = 4 è     4 = A(4) 0       +     B (-2)0  è A + B = 4     (eq. 1)

 

 

a1 = 10  è     10 =     A ( 4) 1       +     B (-2)1  è  4A – 2B = 10   (eq. 2)

 

Then by solving the linear system equations (1) and (2) we can determine the coefficient A and B.

 

(eq.1 ) + 2(eq. 2)   we have

                                                         2A +  2B  = 8

                                                          4A – 2B  = 10

                                                    ------------------------

                                                          6A  =  18

 

è  A  = 3  , then by substitute A = 3 into eq. 1 , we have   3 + B =  4 è B = 1

 

Finally,       an   =  3*(4) n       +     (-2)n