MHB Solve Recurrence Relation w/ 3 Terms & Initial Conditions

[yakin]

How to solve this question. Please explain step by step.

 

[MarkFL]

Hello and welcome to MHB! :D

Can you identify the characteristic equation and its roots?

 

[yakin]

This is all what is given. I have not solved a 3 degree recurrence relation before.

 

[MarkFL]

From the linear homogeneous recurrence, you may obtain the characteristic equation:

$$r^3-2r^2-r+2=0$$

Now, you want to factor this to get its 3 roots. What do you find?

 

[yakin]

I found
r=2
r=1
r=-1

But how did you find the characteristic polynomial equation. I tried, but i got stuck we replace a sub n -1 with r sub n-1. I didn't know what to do next? To get the complete characteristic polynomial.

 

[MarkFL]

Essentially we want to find a solution of the form:

$$a_n=r^n$$

Substituting this solution into the recurrence, we obtain:

$$r^n=2r^{n-1}+r^{n-2}-2r^{n-3}$$

Now, dividing through by $r^{n-3}\ne0$ we obtain:

$$r^3=2r^3+r-2$$

And arranged in standard form, we have:

$$r^3-2r^3-r+2=0$$

Now that you have the characteristic roots, can you state the form of the general solution?

 

[yakin]

Got it. Did the roots i find are correct?

 

[MarkFL]

Got it. Did the roots i find are correct?

Yes, you have the correct roots. So, you want to use these roots to construct the 3-parameter general solution, and then use the given initial values to determine the parameters. You will get a 3X3 linear system of equations to solve.

I've got to run now, (so anyone else is free to jump into answer further questions if they want) but I will be back to check on your progress in roughly 2 hours. :D

 

[yakin]

Whatever you explained so far i redid to get better hang of it. I am going to try to find the closed form, because that is what i need to find. I will post here, whatever i would get, please tell me if i got it correct or wrong, if wrong please explain then. Thanks a lot!

 

[yakin]

I think I'm doing something wrong. not find correct values of alphas 1,2 and 3?

 

[MarkFL]

Try adding the first two equations together and the last two equations together to eliminate the third parameter and then you have a 2X2 system. The subtract one of these two equations from the other to eliminate one of the parameters and then you will be able to solve for the other, and then using that you will be able to determine the values of the other two...

 

[yakin]

Ok i try that!
P.S: Oops i was doing it right the whole time, but just missed one thing when compared my answers with professors' answers. Thanks for reply though!

 

[soroban]

Hello, yakin!

a_n \:=\:2a_{n-1} + a_{n-2} - 2a_{n-2}
. . a_0 = 0,\;a_1 = 1,\;a_2 = 2

You found the characteristic equation and its roots: .2,\,1,\,\text{-}1
Good work!

The closed form will contain powers of these roots:
. . 2^n,\;1^n,\; (\text{-}1)^n

The closed form is a linear combination of these powers.
. . f(n) \;=\;a(2^n) + b(1^n) + c(\text{-}1)^n
and we must determine a,b,c.We know the first three terms of the sequence.

. . \begin{array}{cccccccc}f(0) = 0\!: & a + b + c &=& 0 & [1] \\ f(1) = 1\!: & 2a + b - c &=& 1 & [2] \\ f(2) = 2\!: & 4a + b + c &=& 2 & [3] \end{array}

Solve the system: .a = \tfrac{2}{3},\;b = \text{-}\tfrac{1}{2},\;c = \text{-}\tfrac{1}{6}Therefore: .f(n) \;=\;\tfrac{2}{3}(2^n) - \tfrac{1}{2}(1^n) - \tfrac{1}{6}(\text{-}1)^n

. . . . . . . . f(n) \;=\;\tfrac{1}{6}\left[4\!\cdot\!2^n - 3 - (\text{-}1)^n\right]

. . . . . . . . f(n) \;=\;\tfrac{1}{6}\left[2^{n+2} - 3 + (\text{-}1)^{n+1}\right]