# Recurrence relation, generating function

I am trying to solve this recurrence relation using generating functions $$x_{n+2}+x_{n+1}+x_n=0$$ $$x_0 = x_1=1$$

I have got this generating function $f_a(x)=\frac{2x+1}{x^2+x+1}$. Since the denominator has complex roots I can't factor it. Is there a way to get the series without using complex numbers?

• Isn't this just the periodic sequence repeating (1,1,-2)? – BIS HD Oct 27 '13 at 14:29

Note that $$f(x)=\frac{(1+2x)(1-x)}{(1+x+x^2)(1-x)}=\frac{1+x-2x^2}{1-x^3}=(1+x-2x^2)\sum_{n\geqslant0}x^{3n},$$ hence $$f(x)=\sum_{n\geqslant0}a_nx^{n},\qquad a_{3k}=a_{3k+1}=1,\quad a_{3k+2}=-2,$$ that is, the sequence $(a_n)_{n\geqslant0}$ is $$1,\,1,\,-2,\,1,\,1,\,-2,\,1,\,1,\,-2,\,1,\,1,\,-2,\,1,\,\ldots$$