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...
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.
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 :)
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.
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.)
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
10 comments
[ 0.22 ms ] story [ 25.2 ms ] threadIn 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
It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.
http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...
(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.