## Fibonacci Numbers

Two notes from JiÅ™Ã¬ MatouÅ¡ekâ€™s book *Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra* 1, 2.

**Fibonacci numbers in $O(lg\ n)$ steps**

1.1 Matrix formulation for recursive calculation

$\left( \begin{array}{c}F_{n+2} \ F_{n+1}\end{array} \right) = M\left(\begin{array}{c}F_{n+1}\ F_{n}\end{array}\right) \ for\ M\ =\left(\begin{array}{cc}1 & 1 \ 1 & 0\end{array}\right)\ \therefore \left(\begin{array}{c}F_{n+1}\ F_{n}\end{array}\right) = M^{n}\left(\begin{array}{c}1\ 0\end{array}\right)$

1.2 At most $log_{2}\ n$ multiplications needed size $z <= log_{2}\ n$

$n = 2^a + 2^b +\ â€¦+ 2^z\ for\ a < b <\ â€¦,\ M^n=M^{2^a}M^{2^b}â€¦M^{2^z}$

This can be extended to any recursive formula.

**Fibonacci formula**

2.1 Given the formula

$F_{n+2} = F_{n+1} + F_{n}$

2.2 If we start with the ansatz for either of the two sequences, $u_n$ and $v_n$, that compose $F_n$

$u_n = \tau^{n} \therefore \tau^{n+2} = \tau^{n+1} + \tau^{n}\ \Rightarrow \tau^{2} = \tau + 1$

2.3 This yields two distinct roots

$\tau = (1 \pm \sqrt{5}) / 2$

2.4 The two roots individually form two sequences, **u** and **v**, that are linearly independent. Thus Fibonacci numbers can be written in terms of these basis vectors.

$\mathbf{F} = \alpha \mathbf{u}+ \beta \mathbf{v}$

2.5 The values of Î± and Î² can be evaluation by solving the linear systems, and eventually

$F_n = \frac{1}{\sqrt{5}} \left( (\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^n \right) $

See also: complex Fibonacci.