Last modified on 24 October 2011, at 11:37

Collection of Mathematical Formulas/Fibonacci Numbers

Definition of the Fibonacci sequence:


\begin{cases}
F_0 = 0 \\
F_1 = 1 \\
F_{n+2} = F_n+F_{n+1}, &n = 0, 1, 2, 3, 5, 8 ...
\end{cases}
(1)

[TAOCP1, p. 83], [Concrete, p. 299]:


F_n = \frac{1}{\sqrt{5}} (\phi^n - \hat{\phi}^n), \quad n \in \mathbb{Z}, \quad \phi = \frac{1+\sqrt{5}}{2}, \hat{\phi} = \frac{1-\sqrt{5}}{2}
(2)

[TAOCP1, p. 85]:


F_{n+k} F_{m-k} - F_n F_m = (-1)^n F_{m-n-k} F_k
(2)