Generating Functions and Fibonacci Numbers | Hacker News Reader

Generating Functions and Fibonacci Numbers

austinrochford.com

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.)

http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...

That's great. I had never seen/considered that.

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.

It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.

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.

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

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.

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.

Yeah, sorry, I stand corrected.

No problem.

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 :)

http://en.wikipedia.org/wiki/History_of_combinatorics

Reply on news.ycombinator.com