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...
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
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.
This function gives the Fibonacci number.
integer a = 0
integer b = 1
for i from 1 to n
t = a + b
b = a
a = t