How can I solve the following recurrence relation?
$f(n+1)=f(n)+f(n-1)+f(n-2), \ f(0)=f(1)=f(2)=1.$
I can use the characteristic equation which is $x^3=x^2+x+1$. It has three distinct roots $s,t,r$ therefore the general solution is $f(n)=as^n+bt^n+cr^n.$
On
You essentially mentioned the answer in your question. We can find the characteristic polynomial for the recurrence relation by substituting $f(n) = x^n$ into the relation. This gives $x^{n+1} = x^n + x^{n-1} + x^{n-2}$ and after dividing out by $x^{n-2}$ ($x\neq 0$ by the initial conditions), we get $x^3-x^2-x-1=0$, which has three distinct roots $r,s,t$ (not integers). The general form is $f(n) = as^n + bt^n+cr^n$.
The initial conditions substituted into the equation gives $a+b+c=1, as+bt+cr = 1, as^2+bt^2+cr^2=1$, which can be solved to find $a,b,c$ uniquely.
You're almost done. All that remains is to find $a,b,c$.
Use the initial conditions to get a linear system for $a,b,c$.
You probably won't get nice numbers, because $s,t,r$ are not very nice (see WA).
On the other hand, the matrix in the linear system is a Vandermonde matrix and its inverse can be computed explicitly.