Another way to derive a closed form for the Fibonacci sequence: put the recurrence relation in vector form and solve by finding the eigenvalues. (Which, beautifully, turn out to be the golden ratio and its rational conjugate.)

http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...