How can I determine the general term of a Fibonacci Sequence? Is it possible for any one to calculate F2013 and large numbers like this?
Is there a general formula for the nth term of the Fibonacci Sequence?
If there is a combinatorial formula, that is more preferable; some formula like
Fn = xCy or xPy or something like that for some x and y.
Best Answer
It can be shown that: $$ F_n = \mathop{round}\left(\frac{(1 + \sqrt{5})^n}{2^n \sqrt{5}}\right) $$ but that doesn't help much, as it needs high-precision $\sqrt{5}$.
The other technique is to see that: $$ \begin{pmatrix} F_{n + 2} \\ F_{n + 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n + 1} \\ F_n \end{pmatrix} $$ so that: $$ \begin{pmatrix} F_n \\ F_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n - 1} \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$ You could compute this by diagonalizing the matrix, but that leads to the same trouble as the previous technique (not too surprisingly, the eigenvalues are precisely the troublesome irrational zeros of $z^2 - z - 1$). But if you compute the power of the matrix by an efficient exponentiation method (like exponentiation by squaring) you get a practical algorithm.