Hey there,

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

Given:

Any ideas would be greatly appreciated! Thanks in advance.

Printable View

- November 23rd 2007, 04:07 PMkevi555Solving Recurrence Relations: Characteristic Polynomial
Hey there,

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

Given:

Any ideas would be greatly appreciated! Thanks in advance. - November 23rd 2007, 05:21 PMSoroban
Hello, kevi555!

Quote:

Solve the following recurrence relation.

Given: .

We have: . .**[1]**

Consider the next term:

. . . . . . . .**[2]**

Subtract [1] from [2]: .

. . and we have: .

Divide by

. . and this cubic factors: .

Can you finish it now?

- November 23rd 2007, 06:26 PMkevi555
Thanks for the help.

I think you meant to write

Do I go on to use the equation? Where x1 is -4 and x2 is 1.

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

Thanks! - November 23rd 2007, 06:29 PMgalactus
Here's some more of a hint:

Can you find C, D, E?. This isn't the easiest of recurrence relations to solve. - November 23rd 2007, 08:11 PMkevi555
I tried that method, and if I did it correctly...I end up with...

Does that look right? If not, what should I be doing?

- November 24th 2007, 06:11 AMtopsquark
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

This reproduces both initial conditions.

-Dan - November 24th 2007, 06:41 AMgalactus
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. - November 24th 2007, 07:06 AMtopsquark
- November 24th 2007, 07:26 AMgalactus
Here's what I got using Maple:

The auxiliary equation has one root of multiplicity 2.

- November 24th 2007, 12:58 PMkevi555
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 - November 24th 2007, 02:32 PMtopsquark
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

so we have solutions x = 1, -4, and -4.

Thus the general solution to the recursion equation will be

Now all you need to do is fit and to this. I found I needed a third condition to solve the system completely, and discovered that if I calculated 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:

-Dan - November 24th 2007, 03:07 PMgalactus
Notice the Maple generated solution is the same as topquarks, only in an expanded form. Can't you use 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

- November 25th 2007, 06:24 AMtopsquark
If you have a root z of your auxiliary equation repeated k times, then representing that root we have terms

in the solution to the recursion relation.

So in this case we have the root -4 repeated twice, so we have terms 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 terms in the solution.)

-Dan