[peter_l_downs]

Or you could apply some math and come up with a generating function!

http://www.math.ufl.edu/~joelar/generatingfibonacci.pdf

[antiterra]

And, if you want to know more about generating functions, you can check out the book "generatingfunctionology" by the recently late Herbert Wilf gratis at http://www.math.upenn.edu/~wilf/DownldGF.html

[tmoertel]

Another great resource on generating functions is Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick:

http://algo.inria.fr/flajolet/Publications/book.pdf

[tmoertel]

Another math-y option is to note that the Fibonacci series satisfies the linear recurrence F[n+2] = F[n+1] + F[n] and can therefore be represented in matrix form. Here's a (trimmed down) Maxima session that gives the details:

    $ maxima
    (%i3) load(eigen)$
    (%i4) A: matrix([1, 1], [1, 0])$
    (%i5) b: columnvector([1, 0])$
    (%i6) fib(n) := (''A^^n . ''b)[2][1];

                              <n>
                      [ 1  1 ]      [ 1 ]
    (%o6) fib(n) := (([      ]    . [   ]) )
                      [ 1  0 ]      [ 0 ]
                                          2
                                            1

    (%i7) makelist(fib(n), n, 10);

    (%o7) [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Since the transition matrix A is symmetric, it can be diagonalized using its eigenvector matrix:

    (%i8) similaritytransform(A)$
    (%i9) Adiag: expand(leftmatrix . A . rightmatrix)$

And the n-th power of a diagonal matrix is the same as raising the values on its diagonal to the n-th power:

    (%i10) AdiagN(n) := matrix([''(Adiag[1][1])^n, 0], [0, ''(Adiag[2][2])^n]);

And thus raising A to the n-th power is the same as raising its diagonal counterpart Adiag to that power and then reversing the diagonalization transform (since leftmatrix and rightmatrix are inverses and cancel out for the interior multiplications):

    (%i11) fibdiag(n) := expand(rightmatrix . AdiagN(n) . leftmatrix . b)[2][1]$

Finally, this leads to a closed-form representation for the n-th Fibonacci number:

    (%i12) fibdiag(n);

            sqrt(5)   1 n    1   sqrt(5) n
           (------- + -)    (- - -------)
               2      2      2      2
    (%o12) -------------- - --------------
              sqrt(5)          sqrt(5)

[peter_l_downs]

Very neat, I need to learn more math to truly understand how this works!

[tmoertel]

In that case, pick up a good book on linear algebra. Gilbert Strang's Introduction to Linear Algebra is inexpensive and solid on the fundamentals, and there are related lectures from Strang's MIT course on the subject [1]. Jim Hefferon's Linear Algebra is also good and you can download it for free (GFDL) [2]. It takes a different approach to Strang's book. The two work well together for self-study since for most subjects you can see two different approaches.

Also, for this particular problem, see the "Topic: Linear Recurrences" chapter of Hefferon's book. It actually uses the Fibonacci series as its example (this example seems popular with authors of textbooks and lecture notes).

[1] http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-...

[2] http://joshua.smcvt.edu/linearalgebra/