How do you calculate the nth term in the Fibonacci sequence? - Answers

For low terms, it is probably most economical to to simply list out the sequence until you arrive at the nth term, but for large terms, there actually is a closed-form equation. Let (phi) = (1 + sqrt(5))/2. As an aside, this is the golden ratio. Then the nth term of the Fibonacci sequence is given by F(n) = [(phi)^n - (1 - (phi))^n]/sqrt(5), where we are letting F(0) = 0, F(1) = 1, F(2) = 1, etc. The derivation of this formula involves linear algebra, and, in short, the key is in setting this up as a matrix equation and diagonalizing the matrix. While I shall not run through the process here, I will give you the matrix and vector to start with: Let A be the 2x2 matrix [0 1] [1 1] and x(n) be the column vector in R^2 [F(n)] [F(n+1)] In particular, x(0) = (F(0),F(1)) = (0,1). notice that [A][x(n)] = [F(n+1)] [F(n)+F(n+1)] which is x(n+1). Thus, it follows that x(n) = [A]^n[x(0)] (you can prove this rigorously through induction). Now, F(n) is the first term of the vector x(n), so what one needs to do is diagonalize A, raise A to the appropriate power, multiply it with x(0), and finally take the upper term. The result is what I presented at the outset. Note that with this formula you can show that lim(n-->infinity)[F(n+1)/F(n)] approaches phi.