Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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.

share|cite|improve this question
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

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$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.