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.)<p><a href="http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html" rel="nofollow">http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...</a>
This is a fun example. The formula's easy to prove by induction, but discovering it is less obvious and this is an interesting way.<p>It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.
I've always preferred to write Binet's formula like this:<p>(phi^n - psi^n)/(phi - psi)<p>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 <i>monic</i>, then these are plain integers.<p>This way it looks less surprising that a formula involving irrationals is always rational.<p>To show that the rational is actually an integer, you have to actually perform the division to get<p>phi^n + phi^(n-1) psi + phi^(n-2) psi^2 + ... + psi^n<p>and use the fact that algebraic integers form a ring and the only rational algebraic integers are plain integers.
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.<p>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...