# Factoring $1-(x+x²+x³+x⁴+x⁵)$

I calculated the generating function $G$ of the recurrence:

$$F(0)=0$$ $$F(1)=F(2)=F(3)=F(4)=1$$ $$F(n)=F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)$$

I got:

$$G(x)=\frac{x+x²+x³+x⁴}{1-(x+x²+x³+x⁴+x⁵)}$$

I want to expand this into a series to find the coefficients $\left[ X^n \right] G(X)$. But I can't find a simple way of factoring the denominator of $G(x)$. Here is what I've done so far:

$$S=1-(x+x²+x³+x⁴+x⁵)$$ $$xS=x-(x+x²+x³+x⁴+x⁵+x⁶-x)=x-(S+x⁶-x)$$ $$S(x+1)=2x-x⁶$$ $$S=\frac{2x-x⁶}{x+1}$$

This tells that $0$ is a root of $S$ but plugging $0$ back into $S$ gives $1$! I want hints.

-
The line $xS=x-(S+x^6-x)$ is wrong. It should be $xS=x-(1-S+x^6-x)$. –  user1551 Feb 20 '13 at 13:09
@user1551 Thanks! –  saadtaame Feb 20 '13 at 13:12

## 1 Answer

You have a mistake. The correct term should be: $$S=1-(x+x^2+x^3+x^4+x^5)$$ $$xS=x-(x^2+x^3+x^4+x^5+x^6)=x-(1-S-x+x^6)=2x-x^6-1+S$$ $$S=\frac{2x-x^6-1}{x-1}$$ Therefore $x=0$ is not a root. In fact, the only real root of $S$ is: $$x\sim 0.50866$$

-
Should be $2x-x^6-1+S$ in the second line I think! –  L. F. Feb 20 '13 at 13:23
@L.F. - thanks :) –  nbubis Feb 20 '13 at 13:31
To factor S, one also needs the 4 complex other roots. –  Did Feb 20 '13 at 13:45
@Did - Of course. Unfortunately, none of the roots can be found analytically. I just mentioned the real one to contrast the OP's solution $x=0$. –  nbubis Feb 20 '13 at 14:02