4 ms·
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 mana
by mijoharas 11y ago
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.
- a1k0n 11y agoΣ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.
- alejohausner 11y agoGoogle "fibonacci generating functions", for a more careful derivation. The first hit is: http://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html http://austinrochford.com/posts/2013-11-01-generating-functi...