Physicist. Hells yes! It’s
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
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:
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:
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 x 2 g), 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
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:
with this latest equation we can actually solve for g:
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 “
It so happens (and this is the point of the entire excercise) that functions of the form “
So, with that in mind:
But g was originally defined as n in front of each power of x must be the same as these weird things above.
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 (x 2 +x-1 had factors, but it needn’t have). If that happens, that’s bad…
Don’t know what to tell you.