The Formula for the Fibonacci Sequence

You've probably heard of the Fibonacci sequence.  The one that goes: 1, 1, 2, 3, 5, 8..., where each term is the sum of the last 2.  Maybe you also heard that a formula for these numbers is unknown or hasn't been found, or maybe you have found out that there actually is a formula.  It is surely a problem taught in some math class, and even a quick internet search will bring up the formula.  That formula would happen to be:

Replace the n with a 1 to get the first number in the sequence.  Put in a 2 for the 2nd, 3 for the 3rd, n for the nth...  It still seems strange to me that all those operations on the square root of 5 result in an integer sequence.
The topic reminds me of a Math Biology class last fall.  The professor asked, "How many of you have seen this before?" referring to the formula for the Fibonacci sequence.  I was the only one to raise a hand.  "And where did you see it?"  He asked if it was some math class.  "Uh..."  The answer made me proud, but I also felt a little embarrassed saying it.  "I solved it myself," I said, as normally as I possibly could.

I was an assistant in a high school honors pre-calculus class.  I would have my calculator out to program games and then play them, and I would have my math book out, to look like I was doing something productive with my calculator.  I also listened in to the class, and tried to see if I could solve the problems in my head.  And so, in one class I would hear something about the Fibonacci sequence not having a formula.  I quit the game on my calculator, and started looking at some graphs.
It looked like an exponential sequence, I thought.  I graphed A^x, comparing the values with the values of the Fibonacci sequence, and found that 1.61803... was the best value for A.  What was that number?  Not a rational number or a fraction of pi.  I looked at 1/1.61803 which was .61803.  So it was the number x such that 1/x = x-1.  Or x^2-x-1=0, which, using the quadratic formula, would be (1+sqrt(5))/2 or (1-sqrt(5))/2.  With that number down, I realized that if I thought it was related to an exponential sequence, solving A^(x+2)=A^(x+1) + A^x (because the x+2nd number is the sum of the x+1st and the xth numbers) would have gotten the same result without using graphs and guessing, but that didn't really matter anymore.  I had the numbers, and now I just had to figure out how to combine them.  I happened to try ((1+sqrt(5))/2)^x + ((1-sqrt(5))/2)^x, and I almost had it.  It was a sequence where the next number was the sum of the last 2, just it didn't start with 1 and 1.  I tried various things but couldn't get it right.  I was wondering if that was as close as I would ever get, and then I changed the plus to a minus and saw the answer.  Well, scaled.  I added in the 1/sqrt(5) and there it was.  1, 1, 2, 3, 5, 8, 13...