# Thread: Solving Recurrence Relations: Characteristic Polynomial

1. ## 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.

2. 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?

3. 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!

4. 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.

5. 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?

6. 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

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

8. Originally Posted by topsquark
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

9. 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}$

10. 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

11. Originally Posted by Soroban
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

12. 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}$

13. Originally Posted by galactus
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