Are there alternative formulas for the Fibonacci sequence?

Question

Except for the well known one , using the auxiliary quadratic equation, is there another formula, either using only elementary math or not?

This is a nice elementary alternative which is nearly a formula.

Answer 1

The matrix $$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} $$ calculates Fibonacci numbers. Combined with fast powers (i.e. instead of multiplying $n$ times, you repeatedly square the thing, calculating $A^2, A^4, A^8, \dots$ and combining them to get a $O(\log n)$ algorithm) is a fast way to compute large Fibonacci numbers. This avoids dealing with $(\frac{\sqrt 5 + 1}{2})^n$ which are irrational numbers. If computers store them as floating points, they will lose accuracy and eventually produce wrong answers. If computers perform symbolic calculation, then the computation is essentially the same as the matrix multiplication, but a lot less straightforward.

Answer 2

The Binet formula is well known and there are many other formula's in the OEIS at A000045

Here is a formula which is not listed based on the hypergeometric function $\; _2F_1$

\begin{equation} F_k= \frac{k}{2^{k-1}} {}_2F_1\left(\frac{1-k}{2},\frac{2-k}{2};\frac{3}{2};5\right) = \frac{ \left(1+\sqrt{5}\right)^k-\left(1-\sqrt{5}\right)^k}{2^{k}\sqrt{5}} \end{equation}