I want to solve this recurrence relation; $${ a }_{ n }=3{ a }_{ n-1 }-{ a }_{ n-3 } \quad(n\ge 3) $$$$({ a }_{ 0 }=1,\quad { a }_{ 1 }=3,\quad { a }_{ 2 }=9)$$
First, I use characteristic equation;
$${ x }^{ 3 }-3{ x }^{ 2 }+1=0$$
But, the roots are so complex....
Second, I use generating function $\quad G(x)=\sum _{ n=0 }^{ }{ { a }_{ n }{ x }^{ n } } \quad$ , then I have just this equation; $$G(x)=(1+3x-{ x }^{ 3 })G(x),\quad so\quad G(x)=\frac { 1 }{ 1-3x+{ x }^{ 3 } } $$
Now, I wonder if it is actually possible to get a general solution.