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:


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:


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:


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?