Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 5, 2007 #1
    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

    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.

    (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

    put c1=1 in equation (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: Mar 5, 2007
  2. jcsd
  3. Mar 6, 2007 #2


    User Avatar
    Science Advisor

    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".)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook