SpudTater's formula for approximating the nth Fibonacci number is actually related to a larger formula which calculates the nth number exactly. The formula is:
an=((1+√(5))/2)n-((1-√(5))/2)n
Now the fun part. Why does this work? The reason is that this is the solution to the difference equation defined by the Fibonacci sequence. The Fibonacci sequence is:
an=an-1+an-2
We can form this into a polynomial in Z, where the power of Z is the term in the sequence represented by a, like this:
Zn=Zn-1+Zn-2
Zn-Zn-1-Zn-2=0
Zn-2*(Z2-Z-1)=0
The roots of this equation are 0, ((1+√(5))/2) and (1-√(5))/2). (We can obtain these by using the quadratic formula.) We ignore the trivial root 0, and using the remaining roots we can create the function:
an=c1((1+√(5))/2)n + c2((1-√(5))/2)n
Finally we solve for the constants c1 and c2 by using known values of an (in particular, when n=0 and n=1). We find c1=1 and c2=-1. From this, we get the formula above. Pretty nifty, eh?