# Fibonacci Sequence

Jump to navigation Jump to search
 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