4 ms·
Neat! Not familiar though with generating functions - can you pls explain how the generating function for the Fibonnaci sequence is x/(1 - x - x^2 ) ?
by pitchups 13y ago
Neat! Not familiar though with generating functions - can you pls explain how the generating function for the Fibonnaci sequence is x/(1 - x - x^2 ) ?
- blt 13y agoGenerating functions are amazing. One of the coolest topics in my entire undergrad math degree. This PDF is well written and will explain everything: http://courses.csail.mit.edu/6.042/fall05/ln11.pdf http://courses.csail.mit.edu/6.042/fall05/ln11.pdf
- PhilipTai 13y agoFor Fibonacci sequence, x = 1x^1 x * g(x) = 1x^2 + 1x^3 + 2x^4 + 3x^5 + 5x^6 + ... + x^2 * g(x) = 1x^3 + 1x^4 + 2x^5 + 3x^6 + ... ------------------------------------------------------------ = g(x) = 1x^1 + 1x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + ... Hence, x = (1 - x - x^2) * g(x) g(x) = x / (1 - x - x^2)