# 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:

- = 0
- = 1
- for all .

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

## Properties[edit]

The -th Fibonacci number can be calculated by a closed form formula:

If we rewrite the formula in the following way:

we can see that for the second term goes to zero. In fact, it decreases with increasing , and already for the second term is less than 0.5. Thus we can deduce

### Q-Matrix[edit]

Another interesting approach:

Consider an arbitrary vector . When we multiply it by the matrix , we get the vector . Thus if , then . In general, let , then . As matrix multiplication is associative, we may rewrite the left side of the equation to get . The matrix can be computed in time logarithmic in using repeated squaring.

## Pseudocode[edit]

This function gives the 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