h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

The formula given for generating the Fibonacci sequences is a special case of a more general formula dealing with sequences generated in this manner.

If we say that some sequence S(n) is generated by the formula:
S(n) = A * S(n - 1) + B * S(n - 2)
where A and B are rational numbers;
And we further say that S(0) = 0 and S(1) = 1;
And r1 and r2 are the two roots of the quadratic equation x^2 - Ax - B = 0;
Then:

S(n) = (r1^n - r2^n)/(r1 - r2)

This formula can easily be proven by induction.

For the Fibonacci sequence, A and B are both 1, so the equation x^2 - x - 1 = 0 has the roots (1 + sqrt(5))/2 and (1 - sqrt(5))/2, also known as Phi and 1 - Phi. Also note that Phi - (1 - Phi) = sqrt(5).

Not only that, but the limit of the ratio S(n + 1)/S(n) approaches either r1 or r2 as n goes to infinity. The ratio will approach the root with the largest absolute value. If the roots are imaginary, however, none of this paragraph applies. I would post what happens in that case, but I can't find that page of my notes...Because Phi has a larger absolute value than (1 - Phi), F(n + 1)/F(n) approaches Phi. This can be easily seen with a calculator.

The "standard" sequences describe here all begin 0, 1, .... Sequences starting with other sets of numbers can easily be formed by multiplying and adding "standard" sequences in the appropriate fashion.

All this is my original work (but I'd be surprised if someone else hadn't done it first, so no big deal; I didn't bother to look it up in any books).