Results 1 to 13 of 13

Thread: 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.

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

    Given:
    $\displaystyle 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
    12,028
    Thanks
    848
    Hello, kevi555!

    Solve the following recurrence relation.

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

    Given: .$\displaystyle 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: .$\displaystyle X^{n+1} \:=\:-8X^n - 16X^{n-1} + 5$ .[1]

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


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

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


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

    . . and this cubic factors: .$\displaystyle (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 $\displaystyle (x-1)(x+4)^2$

    Do I go on to use the $\displaystyle 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,002
    Thanks
    1
    Here's some more of a hint:

    $\displaystyle 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...

    $\displaystyle a_{n}= -9.2(1)^{n}+(-0.5+(-0.5)n)(-4)^{n}+(-0.5+(-0.5)n)(-4)^{n}+\frac{1}{5}
    $

    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
    11,152
    Thanks
    731
    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
    $\displaystyle 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; Nov 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,002
    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
    11,152
    Thanks
    731
    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
    $\displaystyle a_n = (2 - A)(-4)^n + \frac{1}{4}(5A - 7)n(-4)^n + A$

    This reproduces both initial conditions.

    -Dan
    Interesting. I used $\displaystyle a_3$ and my series to calculate that $\displaystyle A = \frac{1}{5}$ and can now reproduce the rest of the series. So
    $\displaystyle 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,002
    Thanks
    1
    Here's what I got using Maple:

    $\displaystyle \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.

    $\displaystyle (x-1)(x+4)^{2}$
    Last edited by galactus; Nov 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
    11,152
    Thanks
    731
    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: .$\displaystyle X^{n+1} \:=\:-8X^n - 16X^{n-1} + 5$ .[1]

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


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

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


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

    . . and this cubic factors: .$\displaystyle (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
    $\displaystyle (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
    $\displaystyle a_n = A(1)^n + B(-4)^n + Cn(-4)^n$

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

    Now all you need to do is fit $\displaystyle a_0 = 2$ and $\displaystyle a_1 = -1$ to this. I found I needed a third condition to solve the system completely, and discovered that if I calculated $\displaystyle 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:
    $\displaystyle 2 = B + A$

    $\displaystyle -1 = -4B - 4C + A$

    $\displaystyle -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,002
    Thanks
    1
    Notice the Maple generated solution is the same as topquarks, only in an expanded form. Can't you use $\displaystyle 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
    $\displaystyle 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
    11,152
    Thanks
    731
    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 $\displaystyle 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
    $\displaystyle 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
    $\displaystyle 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 $\displaystyle 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 $\displaystyle \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: Dec 15th 2009, 07:26 AM
  2. Replies: 2
    Last Post: Aug 28th 2009, 12:37 AM
  3. recurrence relations...
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jun 4th 2009, 10:54 PM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM
  5. Solving simultaneous recurrence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 14th 2008, 03:36 PM

Search Tags


/mathhelpforum @mathhelpforum