Results 1 to 13 of 13

Math Help - Solving Recurrence Relations: Characteristic Polynomial

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    7

    Solving Recurrence Relations: Characteristic Polynomial

    Hey there,

    I've been having a bit of trouble solving the following recurrence relation.

    a_{n+1} = -8a_{n} - 16a_{n-1} +5

    Given:
    n\ge 1, a_{0}=2 , a_{1} = -1

    Any ideas would be greatly appreciated! Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539
    Hello, kevi555!

    Solve the following recurrence relation.

    a_{n+1} \:= \:-8a_{n} - 16a_{n-1} +5

    Given: . n \ge 1,\;a_0=2,\;a_1 = -1
    When there is a constant term, I was taught to do it like this . . .


    We have: . X^{n+1} \:=\:-8X^n - 16X^{n-1} + 5 .[1]

    Consider the next term:
    . . . . . . . X^{n+2} \;=\;-8X^{n+1} - 16X^n + 5 .[2]


    Subtract [1] from [2]: . X^{n+2} - X^{n+1} \;=\;-8X^{n+1} + 8X^n - 16X^n + 16X^{n-1}

    . . and we have: . X^{n+2} + 7X^{n+1} + 8X^n - 16X^{n-1} \;=\;0


    Divide by X^{n-1}\!:\;\;X^3 + 7X^2 + 8X - 16 \;=\;0

    . . and this cubic factors: . (X-1)(X-4)^2\;=\;0


    Can you finish it now?

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2007
    Posts
    7
    Thanks for the help.

    I think you meant to write (x-1)(x+4)^2

    Do I go on to use the a_{n} = Cx_{1}^{n} + Dnx_{1}^{n} + Ex_{2}^{n} equation? Where x1 is -4 and x2 is 1.

    Can you help me understand how to find the final equation?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Here's some more of a hint:

    a_{n}=AX^{n}+(B+Bn)X^{n}+(C+Cn)X^{n}+\frac{1}{5}

    Can you find C, D, E?. This isn't the easiest of recurrence relations to solve.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2007
    Posts
    7
    I tried that method, and if I did it correctly...I end up with...

    a_{n}= -9.2(1)^{n}+(-0.5+(-0.5)n)(-4)^{n}+(-0.5+(-0.5)n)(-4)^{n}+\frac{1}{5}<br />

    Does that look right? If not, what should I be doing?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1
    My problem with this is that I need one more condition to get a particular solution? I'm getting a similar form to galactus', but I'm getting an unknown constant that I can't get rid of.

    My solution so far is
    a_n = (2 - A)(-4)^n + \frac{1}{4}(5A - 7)n(-4)^n + A

    This reproduces both initial conditions.

    -Dan
    Last edited by topsquark; November 24th 2007 at 06:54 AM. Reason: Fixed a typo.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    I must admit, I tried as you TP and kept heading in the wrong direction.

    I ran it through Maple and that is what it gave me.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1
    Quote Originally Posted by topsquark View Post
    My problem with this is that I need one more condition to get a particular solution? I'm getting a similar form to galactus', but I'm getting an unknown constant that I can't get rid of.

    My solution so far is
    a_n = (2 - A)(-4)^n + \frac{1}{4}(5A - 7)n(-4)^n + A

    This reproduces both initial conditions.

    -Dan
    Interesting. I used a_3 and my series to calculate that A = \frac{1}{5} and can now reproduce the rest of the series. So
    a_n = \frac{9}{5}(-4)^n - \frac{3}{2}n(-4)^n + \frac{1}{5}

    Why didn't we need a third condition? Because there were only two distinct roots to the auxiliary equation?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Here's what I got using Maple:

    \frac{33}{10}(-4)^{n}+(\frac{-7}{4}n-\frac{7}{4})(-4)^{n}+(\frac{1}{4}n+\frac{1}{4})(-4)^{n}+\frac{1}{5}

    The auxiliary equation has one root of multiplicity 2.

    (x-1)(x+4)^{2}
    Last edited by galactus; November 24th 2007 at 07:39 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2007
    Posts
    7
    Topsquark's eqn seems to work fine, I'm just having a bit of difficulty understanding what general formula you are using. Where does 1/5 come from? If you could explain it, I'd appreciate it! Thanks

    Kev
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1
    Quote Originally Posted by Soroban View Post
    Hello, kevi555!

    When there is a constant term, I was taught to do it like this . . .


    We have: . X^{n+1} \:=\:-8X^n - 16X^{n-1} + 5 .[1]

    Consider the next term:
    . . . . . . . X^{n+2} \;=\;-8X^{n+1} - 16X^n + 5 .[2]


    Subtract [1] from [2]: . X^{n+2} - X^{n+1} \;=\;-8X^{n+1} + 8X^n - 16X^n + 16X^{n-1}

    . . and we have: . X^{n+2} + 7X^{n+1} + 8X^n - 16X^{n-1} \;=\;0


    Divide by X^{n-1}\!:\;\;X^3 + 7X^2 + 8X - 16 \;=\;0

    . . and this cubic factors: . (X-1)(X-4)^2\;=\;0


    Can you finish it now?

    I'll pick it up from this point. (Odd, I had thought that Soroban had the solution to the cubic correct earlier.)

    The cubic factors to
    (x - 1)(x + 4)^2 = 0
    so we have solutions x = 1, -4, and -4.

    Thus the general solution to the recursion equation will be
    a_n = A(1)^n + B(-4)^n + Cn(-4)^n

    a_n = B(-4)^n + Cn(-4)^n + A

    Now all you need to do is fit a_0 = 2 and a_1 = -1 to this. I found I needed a third condition to solve the system completely, and discovered that if I calculated a_2 from the original recursion relation, I could set n = 2 in my solution and thus get a third relationship from which I could eliminate A.

    So the problem essentially boils down to solving the system:
    2 = B + A

    -1 = -4B - 4C + A

    -19 = 16B + 32C + A

    -Dan
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Notice the Maple generated solution is the same as topquarks, only in an expanded form. Can't you use AX^{n}+BnX^{n}+Cn^{2}X^{n} when you have three terms?. I tried and kept getting the incorrect solution. So, either I done it wrong or I am misconstrued. What are your thoughts?.

    I thought with recursions, when you have k terms, you could set it up as
    C_{1}X^{n}+C_{2}nX^{n}+..........+C_{k}n^{k-1}X^{n}
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1
    Quote Originally Posted by galactus View Post
    Notice the Maple generated solution is the same as topquarks, only in an expanded form. Can't you use AX^{n}+BnX^{n}+Cn^{2}X^{n} when you have three terms?. I tried and kept getting the incorrect solution. So, either I done it wrong or I am misconstrued. What are your thoughts?.

    I thought with recursions, when you have k terms, you could set it up as
    C_{1}X^{n}+C_{2}nX^{n}+..........+C_{k}n^{k-1}X^{n}
    If you have a root z of your auxiliary equation repeated k times, then representing that root we have terms
    Az^n + Bnz^n + ~...~ + Cn^{k-1}z^n
    in the solution to the recursion relation.

    So in this case we have the root -4 repeated twice, so we have terms B(-4)^n + Cn(-4)^n in the solution.

    (This is all very similar to solving a linear differential equation with constant coefficients and having repeated roots to the auxiliary equation producing \sum_{j = 1}^k A_jx^{j - 1}e^{zx} terms in the solution.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 15th 2009, 07:26 AM
  2. Replies: 2
    Last Post: August 28th 2009, 12:37 AM
  3. recurrence relations...
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 4th 2009, 10:54 PM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  5. Solving simultaneous recurrence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 14th 2008, 03:36 PM

Search Tags


/mathhelpforum @mathhelpforum