# Fibonacci Sequence

(Redirected from Fibonacci)
 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:

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

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

## Properties

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

If we rewrite the formula in the following way:

${\displaystyle 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 ${\displaystyle n\to \infty }$ the second term goes to zero. In fact, it decreases with increasing ${\displaystyle n}$, and already for ${\displaystyle n=0}$ the second term is less than 0.5. Thus we can deduce ${\displaystyle 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 ${\displaystyle v=(a,b)}$. When we multiply it by the matrix ${\displaystyle A=\left({0~1 \atop 1~1}\right)}$, we get the vector ${\displaystyle vA=(b,ab)}$. Thus if ${\displaystyle v=(F_{n},F_{n1})}$, then ${\displaystyle vA=(F_{n1},F_{n}F_{n1})=(F_{n1},F_{n2})}$. In general, let ${\displaystyle v=(F_{0},F_{1})}$, then ${\displaystyle (\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 ${\displaystyle vA^{n}}$. The matrix ${\displaystyle A^{n}}$ can be computed in time logarithmic in ${\displaystyle n}$ using repeated squaring.

## Pseudocode

This function gives the ${\displaystyle 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