Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Is anyone able to show how you get from this line:

ΣnFib(n+2)x^(n+2)=ΣnFib(n+1)x^(n+2)+ΣnFib(n)x^(n+2)

to this one:

F(x)−x−1=x(F(x)−1)+x2F(x)

I haven't managed to figure it out and have a couple of colleagues that haven't been able to work it out as well.



ΣnFib(n+2)x^(n+2) is F(x)−x−1 because it's an infinite series of powers of x, except since it's x^(n+2) then x^1 (x) and x^0 (1) never appear, so you need to subtract them from F(x) which is ΣnFib(n)x^n. I hope that's clear and explains the rest.


Google "fibonacci generating functions", for a more careful derivation. The first hit is: http://austinrochford.com/posts/2013-11-01-generating-functi...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: