# Solving Recurrence Relations: Characteristic Polynomial

• Nov 23rd 2007, 04:07 PM
kevi555
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.
• Nov 23rd 2007, 05:21 PM
Soroban
Hello, kevi555!

Quote:

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?

• Nov 23rd 2007, 06:26 PM
kevi555
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!
• Nov 23rd 2007, 06:29 PM
galactus
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.
• Nov 23rd 2007, 08:11 PM
kevi555
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}
$

Does that look right? If not, what should I be doing?
• Nov 24th 2007, 06:11 AM
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
$a_n = (2 - A)(-4)^n + \frac{1}{4}(5A - 7)n(-4)^n + A$

This reproduces both initial conditions.

-Dan
• Nov 24th 2007, 06:41 AM
galactus
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.
• Nov 24th 2007, 07:06 AM
topsquark
Quote:

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
$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
• Nov 24th 2007, 07:26 AM
galactus
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}$
• Nov 24th 2007, 12:58 PM
kevi555
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
• Nov 24th 2007, 02:32 PM
topsquark
Quote:

Originally Posted by Soroban
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
• Nov 24th 2007, 03:07 PM
galactus
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}$
• Nov 25th 2007, 06:24 AM
topsquark
Quote:

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