Fibonacci Sequence

From Algorithmist
Jump to: navigation, 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[edit]

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[edit]

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[edit]

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

External Links[edit]