Fibonacci Sequence

From Algorithmist
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:

  • = 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.

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

External Links[edit]