Re:Generating Functions and Fibonacci Numbers
by sigil on Saturday November 02, 2013 @06:02PM
(#6661023)
Another way to derive a closed form for the Fibonacci sequence: put the recurrence relation in vector form and solve by finding the eigenvalues. (Which, beautifully, turn out to be the golden ratio and its rational conjugate.)
Re:Generating Functions and Fibonacci Numbers
by btilly on Saturday November 02, 2013 @06:52PM
(#6661205)
There are actually perfectly routine ways to discover formulas like this one for this type of equation. See http://en.wikipedia.org/wiki/Recurrence_relation for some of the theory behind how to do it.
Re:Generating Functions and Fibonacci Numbers
by jordigh on Saturday November 02, 2013 @08:39PM
(#6661550)
I've always preferred to write Binet's formula like this:
(phi^n - psi^n)/(phi - psi)
The only difference is writing the sqrt(5) denominator as phi-psi. The reason being, this exhibits that the Fibonacci numbers are a symmetric function of the roots of a polynomial. Thus, even though phi and psi involve irrational numbers, this symmetric function of them must be in the base rational field, and since the polynomial x^2 - x - 1 is monic, then these are plain integers.
This way it looks less surprising that a formula involving irrationals is always rational.
To show that the rational is actually an integer, you have to actually perform the division to get
Re:Generating Functions and Fibonacci Numbers
by jkarni on Saturday November 02, 2013 @04:02PM
(#6660526)
This is pretty close to Knuth's discussion of Fibonacci Numbers in TAOCP. I'm inclined that's where this came from, and that this is missing an attribution.
In either case, if you enjoyed this post add one to the "I-should-read-TAOCP" (or "I-should-continue-reading-TAOCP") tally. I did...
Re:Generating Functions and Fibonacci Numbers
by deSouza on Saturday November 02, 2013 @05:58PM
(#6661005)
Knuth is great, but if we are going to attribute this derivation, we have to go far longer back in time. De Moivre was the first to derive a closed formula for the Fibonacci numbers, and he did so by "inventing" generating functions. I only have wikipedia as a source right now, as I have most of my math books, including the few on the history of mathematics I have, in boxes :)
Re:Generating Functions and Fibonacci Numbers
by MidsizeBlowfish on Saturday November 02, 2013 @04:13PM
(#6660567)
OP here, I have actually not read TAOCP at all. It's just a derivation I sometimes use to pass a few minutes while waiting/bored and I thought I'd blog about it.
http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...
It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.
(phi^n - psi^n)/(phi - psi)
The only difference is writing the sqrt(5) denominator as phi-psi. The reason being, this exhibits that the Fibonacci numbers are a symmetric function of the roots of a polynomial. Thus, even though phi and psi involve irrational numbers, this symmetric function of them must be in the base rational field, and since the polynomial x^2 - x - 1 is monic, then these are plain integers.
This way it looks less surprising that a formula involving irrationals is always rational.
To show that the rational is actually an integer, you have to actually perform the division to get
phi^n + phi^(n-1) psi + phi^(n-2) psi^2 + ... + psi^n
and use the fact that algebraic integers form a ring and the only rational algebraic integers are plain integers.
In either case, if you enjoyed this post add one to the "I-should-read-TAOCP" (or "I-should-continue-reading-TAOCP") tally. I did...
http://en.wikipedia.org/wiki/History_of_combinatorics