Fibonacci Sequence

 This is a stub or unfinished. Contribute by editing me.

The Fibonacci Sequence is a sequence that appears often in nature. It is usually defined with:

• $a_{0}$ = 0
• $a_{1}$ = 1
• $a_{i}=a_{{i-1}}a_{{i-2}}$ for all $i\geq 2$.

The first few terms are: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Properties

The $N$-th Fibonacci number can be calculated by a closed form formula: $F_{n}={\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n}}{2^{n}{\sqrt {5}}}}$

If we rewrite the formula in the following way:

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

we can see that for $n\to \infty$ the second term goes to zero. In fact, it decreases with increasing $n$, and already for $n=0$ the second term is less than 0.5. Thus we can deduce $F_{n}={{\rm {round}}}\left({\frac {1}{{\sqrt {5}}}}\cdot \left({\frac {{\sqrt {5}}1}{2}}\right)^{n}\right)$

Q-Matrix

Another interesting approach:

Consider an arbitrary vector $v=(a,b)$. When we multiply it by the matrix $A=\left({0~1 \atop 1~1}\right)$, we get the vector $vA=(b,ab)$. Thus if $v=(F_{n},F_{{n1}})$, then $vA=(F_{{n1}},F_{n}F_{{n1}})=(F_{{n1}},F_{{n2}})$. In general, let $v=(F_{0},F_{1})$, then $(\dots ((v\underbrace {A)A)\dots )}_{{n{{\rm {~times}}}}}=(F_{n},F_{{n1}})$. As matrix multiplication is associative, we may rewrite the left side of the equation to get $vA^{n}$. The matrix $A^{n}$ can be computed in time logarithmic in $n$ using repeated squaring.

Pseudocode

This function gives the $nth$ Fibonacci number.

function fib(n)
integer a = 0
integer b = 1
integer t

for i from 1 to n
t = a + b
b = a
a = t
return a