Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

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

 
discard

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.