Linear recurrence

Question

I'm having a lot of problems with this one linear recurrence problem ...

First, verify that: $x^3 − 3x − 2 = (x^2 + 2x + 1)(x − 2). $

Then, solve the linear recurrence   
f(0) = 0, f(1) = 1, f(2) = 7,   
f(n) = 3f(n − 2) + 2f(n − 3).

I'm able to get this far but I don't know how to continue because of the cube roots.

$f(n) = x^n $

$x^n = 3x^{n-2} + 2x^{n-3} $

$x^3 = 3x + 2 $

$x^3 - 3x - 2 = 0 $

Answer 1

you wrote the answer: "verify that: $x^3 − 3x − 2 = (x^2 + 2x + 1)(x − 2)$".

solve that polynomials separately:

$ x-2=0$ and $x^2 + 2x + 1=0$.

Answer 2

For the recurrence relation $$f(n) = 3f(n − 2) + 2f(n − 3)$$ the characteristic equation is $$r^3=3r^2+2$$ which is exactly the equation you had to solve at the beginning; using D.A.'s answer, the solutions are then $r=2$, $r=-1$, $r=-1$. So, because of the double root, the solution will be $$f(n)=c_1(2)^n+c_2(-1)^n+c_3(-1)^nn$$ Now, apply the conditions you are given $f(0) = 0, f(1) = 1, f(2) = 7$. This will give you three simple linear equations in $c_1,c_2,c_3$.

I am sure that you can take from here.

Edit

If I may suggest, I suppose that it could be a good idea to establish the formula separatly for odd and even values of $n$.