Physicist: Hells yes! It’s , where the “≈” is close enough that you can round to the nearest integer. Astute readers will notice that is the golden ratio, and may wonder if this is a coincidence. Yes.
Everything after this is a detailed, math-heavy explanation of where this formula comes from.
The “Fibonacci sequence” is defined as a sequence of numbers such that you have the recursion: , and the restrictions: and .
Explicitly, the Fibonacci sequence is: 1, 1, 2, 3, 5, 8, 13, 21, … That is, the recursion says that every term is the sum of the previous two.
You can also talk about “generalized Fibonacci sequences”, where these restrictions and/or the recursion are changed. For example: , with and . This derivation is for the ordinary sequence, but it can be altered to suit any generalized Fibonacci sequence. Here it is:
Every now and again it’s useful to encode a string of numbers in a “generating function“. For obscure (and unimportant to this post) reasons, you can write many functions as infinitely long polynomials. For example: . The generating function for a sequence of numbers is . So, sin(x) is the generating function for the sequence . If you can find a simple form for this function g, then bully. You’ve got a very straight forward way of writing an infinite string of numbers. The value of x doesn’t have anything to do with anything. The powers of x are really just there to keep the numbers straight. Now check this out!
You can take the recursion and use it to find a relationship between these three slightly different functions. Here’s a good first guess:
You can write this out, group by powers of x, and then use the recursion. However (if you look at the definitions above for g, xg, and x2g), each sum starts at a different value of n. That needs to be dealt with first:
ii) pulling out the n=0,1 terms
iii-iv) grouping by powers of x
v) fn = fn-1+fn-2
vi) f0 =1 and f1=1
This doesn’t quite line up, so the guess wasn’t perfect. There should have been an extra “+1″ on the right side of the original equation:
Armed with this latest equation we can actually solve for g:
Here and . The only reason for writing it this way is that leaving all those roots and fractions in makes this look like a math blizzard.
So far, using what is known about the Fibonacci sequence, we’ve found a nice closed equation for the generating function (g), which “encodes” the sequence. Hopefully, we can use this fancy new equation to figure out what each fn must be. Again, the function (g) itself does nothing. The only reason it’s around is so that we can look at the coefficients when it’s written in the form of a (Taylor) polynomial.
Now using “partial fractions” you can pull this one kinda-complicated fraction into two no-so-complicated fractions (that’s where the “” comes from):
It so happens (and this is the point of the entire excercise) that functions of the form “” can be written as: . This is called a “geometric series“. For example: .
So, with that in mind:
But g was originally defined as . These fn in front of each power of x must be the same as these weird things above.
Notice: 1) is the golden ratio (not that it matters), and 2) . This means that the second term is smaller than one, and each successive power is progressively smaller. So, rather than calculate it, ignore it!
Were you so inclined you could take any initial conditions (the f0 and f1) and any recursion (of the form fn = Afn-1+Bfn-2) and, using the method above, find a closed form for it as well. The only problem you may run into is finding yourself with a polynomial that can’t be factored (x2+x-1 had factors, but it needn’t have). If that happens, that’s bad…
Don’t know what to tell you.