Solve the recurrence relation a_n = a_n-1 + 20a_n-2

[hyderman]

hello
please check my answer and let me know if there are any errors and if there are better ways to solve ......



Solve the recurrence relation

an = an−1 + 20an−2

with a0 = −1 and a1 = 13.




Step – I : Find Characteristic equation and solve for its roots:

an = an−1 + 20an−2 ------equation (0)

First of all make corresponding characteristic equation of equation 0 and find roots of that equation

let
an= r2
an-1 =r
an-2 =r0

Substituting above values in equation (0)
r2 =r + 20


r2-r-20=0 is the characteristic equation.

r2-5r+4r-20=0
r(r-5)+4(r-5)=0
(r-5 ) (r+4)=0

r1 = 5 , r2 = -4 are the roots of this characteristic equation

Step– II : Find Constants’ value using Initial Condition

So solution of this polynomial would be

an = c1 r1n + c2 r2n ------------------equation (1)



Where c1 & c2 are some arbitrary constants .

Now we have to find values of c1 and c2 using Initial Condition.


As a0 = −1 and a1 = 13.

So put n=0 in equation (1)

a0= c1 r10 + c2 r20
a0= c1 + c2
-1 = c1 + c2 ---------equation (2)

Now put n=1 in equation (1)
a1 = c1 r11 + c2 r21

13= c1 (5)1 + c2 (-4)1 --------------equation (3)


Multiply equation (2) by 4

-4= 4c1 + 4c2 -------------------------------------------------equation (4)

Add equation (3) and (4) to get the values of c1 & c2.
-4= 4c1 + 4c2
13= 5c1 - 4c2

9 = 9c1
c1=1

put c1=1 in equation (2)

c2=-2

Step-III ..Substitute values of c1 , c2 , r1 and r2 to get the final solution

so substituting these values in equation
an = 1.5n + (-2) 4n


an = 5n – (2).4n is the final solution of this recurrence relation

 

[HallsofIvy]

Why can't you check your answer yourself? Put your solution
a_n= 5ⁿ-2(-4)ⁿ into the recurrance equation and see if it satisfies it. It's obvious that it has the right values for a₀ and a₁.

By the way, if you don't want to use [ sub ] and [ /sub ] (without the spaces) to get subscripts, at least use underscores and parentheses: a_n= a_(n-1)+ 20a_(n-2) is not at all the same as a_n= a_n-1+ 20 a_n- 2!!
(and r^n makes more sense than "rn".)