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:

a_{n}=((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:

a_{n}=a_{n-1}+a_{n-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:

Z^{n}=Z^{n-1}+Z^{n-2}

Z^{n}-Z^{n-1}-Z^{n-2}=0

Z^{n-2}*(Z^{2}-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:

a_{n}=c_{1}((1+√(5))/2)^{n} + c_{2}((1-√(5))/2)^{n}

Finally we solve for the constants c_{1} and c_{2} by using known values of a_{n} (in particular, when n=0 and n=1). We find c_{1}=1 and c_{2}=-1. From this, we get the formula above. Pretty nifty, eh?