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

Answer 1

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.