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

How to solve recurrence relation ?

  1. May 8, 2010 #1
    How to solve recurrence relation ???

    The Example is ;

    Solve the recurrence relation a n + 2a n-1 + 2a n-2 = 0 where n ≥ 2 and a 0 = 1 a 1 = 3
    a n = nth order
    a n-1 = (n-1)th order.
    a n-2 = (n-2)th order.

    I've started the solving ;
    a n = r^n
    so
    the equation will be ;

    r^n + 2r^(n-1) + 2r^(n-2)
    r^2 + 2r + 2 = 0
    I could'nt do anything after find the roots ?
    What should i do ?
    Thanks for helping.
     
  2. jcsd
  3. May 8, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi jjosephh! Welcome to PF! :smile:

    (try using the X2 and X2 tags just above the Reply box :wink:)
    If your characteristic equation, r2 + 2r + 2 = 0, has roots p and q,

    then the general soultion will be linear combinations of solutions to the equations

    an = pan-1 and an = qan-1 :smile:
     
  4. May 8, 2010 #3
    Re: How to solve recurrence relation ???

    The problem is ;
    Solve the recurrence relation a n + 2a(n-1) + 2a(n-2) = 0 where n ≥ 2 and a0 = 1 a 1 = 3

    I said;

    a n = rn

    and found this equation ;

    r2 + 2r +2 = 0

    I have to find r1 and r2 to write ;

    K1r12 + K2r22 = a n
    I know a0 and a 1 so i can find K1 and K2

    But i have problem with roots :)
     
  5. May 8, 2010 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Re: How to solve recurrence relation ???

    Use the quadratic formula. You'll have two complex roots (conjugates, naturally).
     
  6. May 8, 2010 #5
    Re: How to solve recurrence relation ???

    I found

    r1 = -1 -i
    r2 = -1 +i

    an = K1 r1n + K2 r2n

    I'm trying to find K1 and K2

    a0 = 1 => K1 + K2 = 1
    a1 = 3 => K1(-1-i) + K2(-1+i) = 3

    Can you help me to find K1 and K2
     
  7. May 8, 2010 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi jjosephh! :wink:
    From the first equation, K2 = 1 - K1, so put that in the second equation, and that gives you an equation for K1. :smile:
     
  8. May 8, 2010 #7
    Re: How to solve recurrence relation ???

    Thank you for all helps
    I have another question ;
    Solve the recurrence relation
    an+2 - 6an+1 + 9an = 3*2n + 7*3n
    where n>=0 and a0 = 1 a1 = 4

    I think there are two path to solve this problem.
    First path is find homogenous solution and the second is particular solution
    So ;
    In homog. solution i found r1 and r2 are both equal to 3.If roots are equal what should i do ? Or the roots are correct ?
    Thanks for all advices .
     
  9. May 8, 2010 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    The two independent solutions are an = 3n and an = n3n :smile:
     
  10. May 8, 2010 #9
    Re: How to solve recurrence relation ???

    When you have multiple roots, you must multiply the term with a polynomial. For double roots, the polynomial is n+1, and for triple roots, it's [tex]\frac{\left(n+1\right)\left(n+2\right)}2[/tex], etc.

    We extend the definition of a to the negative domain, and let [tex]a_n=0[/tex] for [tex]n<0[/tex]. Then we find the value of [tex]a_{n+2}-6a_{n+1}+9a_n[/tex] for [tex]n<0[/tex].

    [tex]a_1-6a_0+9a_{-1}=-2[/tex]
    [tex]a_0-6a_{-1}+9a_{-2}=1[/tex]
    [tex]a_{n+2}-6a_{n+1}+9a_n=0[/tex] for [tex]n<-2[/tex].

    Then the equation becomes:
    [tex]a_{n+2}-6a_{n+1}+9a_n=H\left[n\right]\left(3\cdot 2^n+7\cdot 3^n\right)-2\delta\left[n+2\right]+\delta\left[n+1\right][/tex], where H is the unit step function.

    The Z-transform of this equation is:
    [tex]A\left(z\right)=\frac{\frac 3{1-2z^{-1}}+\frac 7{1-3z^{-1}}-2z^2+z}{\left(z^2-6z+9\right)}=\frac{\frac 3{1-2z^{-1}}+\frac 7{1-3z^{-1}}-2z^2+z}{\left(z-3\right)^2}=\frac{3\left(1-3z^{-1}\right)+7\left(1-2z^{-1}\right)+\left(z-2z^2\right)\left(1-5z^{-1}+6z^{-2}\right)}{\left(1-2z^{-1}\right)\left(1-3z^{-1}\right)\left(z-3\right)^2}=[/tex]
    [tex]\frac{z^2-6z+1+17z^{-1}}{\left(1-2z^{-1}\right)\left(1-3z^{-1}\right)\left(z-3\right)^2}=[/tex]
    [tex]\frac{z^4-6z^3+z^2+17z}{\left(z-2\right)\left(z-3\right)^3}[/tex]
    We can write this as:
    [tex]A\left(z\right)=\frac P{z-2}+\frac {Qz^2+Rz+S}{\left(z-3\right)^3}[/tex]
    Then:
    [tex]P\left(z-3\right)^3+\left(Qz^2+Rz+S\right)\left(z-2\right)=P\left(z^3-9z^2+27z-27\right)+Q\left(z^3-2z^2\right)+R\left(z^2-2z\right)+S\left(z-2\right)=z^4-6z^3+z^2+17z[/tex]
    We can try solving it in this way:
    [tex]P+Q=0[/tex]
    [tex]-9P-2Q+R=0[/tex]
    [tex]27P-2R+S=0[/tex]
    [tex]-27P-2S=z^4-6z^3+z^2+17z[/tex]
    This has the following solution:
    [tex]P=-z^4+6z^3-z^2-17z[/tex]
    [tex]Q=z^4-6z^3+z^2+17z[/tex]
    [tex]R=-7z^4+42z^3-7z^2-119z[/tex]
    [tex]S=13z^4-78z^3+13z^2-221z[/tex]
    The inverse Z-transform of [tex]\frac{-z^4+6z^3-z^2-17z}{z-2}+\frac {13z^6-85z^5+56z^4+208z^3-118z^2+17z}{\left(z-3\right)^3}[/tex] is:
    [tex]2^n\left(-8H\left[n+3\right]+24H\left[n+2\right]-2H\left[n+1\right]-17H\left[n\right]\right)+[/tex]
    [tex]\frac{3^n}2\left(351H\left[n+3\right]\left(n+4\right)\left(n+5\right)-765H\left[n+2\right]\left(n+3\right)\left(n+4\right)+168H\left[n+1\right]\left(n+2\right)\left(n+3\right)+[/tex]
    [tex]208H\left[n\right]\left(n+1\right)\left(n+2\right)-\frac{118}3H\left[n-1\right]\left n\left(n+1\right)+\frac{17}9H\left[n-2\right]\left(n-1\right)n\right)[/tex]
    So, that's your function, if my calculations are correct. If not, just follow this general method and you should get the correct answer. It can be simplified further by ignoring the H's and adding all the terms containing n.
     
  11. May 9, 2010 #10

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    (just got up :zzz: …)
    Z-transform ??

    jjosephh, ignore this very complicated method and just do it the way you were going to! :smile:
     
  12. May 9, 2010 #11
    Re: How to solve recurrence relation ???

    Yeah, I don't know if there's a simpler way to solve this, but remember that when you take into account the right hand side, the equation has four roots, three of which are 3 and one that is 2. So, the solution must have the form:
    [tex]a_n=A2^n+(B+Cn+Dn^2)3^n[/tex]
     
  13. May 27, 2010 #12
    Re: How to solve recurrence relation ???

    Hello again,
    an+2 - 6an+1 + 9an = 3*2n + 7*3n

    what about the particular solution ?
    should be f(n) = B12n + B23n
     
  14. May 27, 2010 #13

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hello again jjosephh! :smile:

    I assume that you've got B1 but you've found the same method doesn't work for B2 ? :redface:

    Start by trying the same trick that you're using for the ("= 0") general solution. :wink:
     
  15. May 27, 2010 #14
    Re: How to solve recurrence relation ???

    you mean ;
    f(n) = B1(2n + 3n)
    ??
     
  16. May 27, 2010 #15

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No … go back to B12n + B23n

    what did you get for B1 ?
     
  17. May 27, 2010 #16
    Re: How to solve recurrence relation ???

    B1 = 3
    B2 = -7/9
    and the solution is ;
    (I got before hom. solution A1= -11/9 A2 = 4/3)
    an = -11/9*2n + 4/3*3n +3*2n -7/93n
     
  18. May 27, 2010 #17
    Re: How to solve recurrence relation ???

    by the way a(0) = 1and a(1)=4
    n>=2
     
  19. May 27, 2010 #18

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    I'm confused … how did you get that homogeneous solution from an+2 - 6an+1 + 9an ? :confused:

    (and I get your B1, but not your B2)
     
  20. May 27, 2010 #19
    Re: How to solve recurrence relation ???

    r1,r2 = 3
    so the solution must be
    an+2 = rn
    an+2 = A1*r1n + A2*n*r2n

    an+2 = A1*31n + A2*n*32n

    I think i need help :)
     
  21. May 27, 2010 #20

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    he he :biggrin:

    No, if two roots of the characteristic equation are the same, you use Arn + Bnrn (three roots the same, + Cn2rn and so on …)

    in this case, (A + Bn)3n :smile:

    (and that should help you with the particular solution :wink:)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook