Fibonacci Sequence

From Algorithmist

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

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

[edit] 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 $v A = (b, a b)$ . Thus if $v = (F n, F n 1)$ , then $v A = (F n 1, F n F n 1) = (F n 1, F n 2)$ . In general, let $v = (F 0, F 1)$ , then $(\dots((v\underbrace{A)A)\dots)}_{n{\rm~times}} = (F_n,F_{n 1})$ . As matrix multiplication is associative, we may rewrite the left side of the equation to get $v A n$ . The matrix $A n$ can be computed in time logarithmic in $n$ using repeated squaring.

[edit] Pseudocode

This function gives the $n t h$ Fibonacci number.

function fib(n)
    integer a = 1
    integer b = 0
    integer t

    for i from 1 to n
        t = a   b
        b = a
        a = t
    return a

[edit] External Links

Fibonacci Sequence

From Algorithmist

Contents

[edit] Properties

[edit] Q-Matrix

[edit] Pseudocode

[edit] External Links

Views

Personal tools

Navigation

Search

Toolbox