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

  • Thread starter hyderman
  • Start date
  • #1
30
0
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
 
Last edited:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
962
Why can't you check your answer yourself? Put your solution
an= 5n-2(-4)n into the recurrance equation and see if it satisfies it. It's obvious that it has the right values for a0 and a1.

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".)
 

Related Threads on Solve the recurrence relation a_n = a_n-1 + 20a_n-2

  • Last Post
2
Replies
29
Views
2K
  • Last Post
Replies
3
Views
708
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
805
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
14
Views
977
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
482
Top