Fibonacci Series

Fibonacci Series is famous sequence of numbers each the sum of its two immediate predecessors. It was developed by Italian mathematician Leonardo Fibonacci.

Fn    =      Fn-1+Fn-2     if n>1
                1                   if n=1
                0                   if n=0

In fact, the Fibonacci numbers grow almost as fast as powers of 2: e.g. F30 is over a million, and F100 is already 21 digits longs. In general, Fn=2(0.694n)

Recursive algorithm.

pseudo code

function fib1(n)
if n=0: return 0
if n=1: return 1
return fib1(n-1) + fib1(n-2)

Time Complexity

Let Tn be the number of computer steps needed to compute fib1(n). so if n is less than 2, the procedure halts immediately.
therefore, T(n) <=2 for n<=1

For larger values of n, there are two recursive invocation of fib1, taking time, T(n-1) and T(n-2) respectively, plus three computer steps.
therfore, T(n)=T(n-1)+T(n-2)+3 for n>1

comparing this to the recurrence relation for Fn, we see T(n)>=Fn.
Hence, the running time of the algorithm grows as fast as the Fibonacci numbers! T(n) is exponential in n, which implies that the algorithm is impractically slow except for very small values of n.

Can we do better?

Iterative algorithm

A more sensible scheme would store the intermediate results — the values F0,F1,...,Fn-1 soon as they become known.
pseudo code

function fib2(n)
if n = 0 return 0
create an array f[0...n]
f[0] = 0, f[1] = 1
for i = 2...n:
f[i] = f[i-1] + f[i-2]
return f[n]

Time Complexity

The inner loop consists of a single computer step and n is executed n1 times. Therefore the number of computer steps used by fib2 is linear in n.

Can we do better?

One idea involves matrices.
we start by writing the equations F1=F1 and F2=F0+F1 in matrix notation:

Here, calculation of matrix coefficient will take approx log(n) complexity.

Applications of Fibonacci Numbers

The Fibonacci numbers are important in the run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers.

The Fibonacci numbers occur in a formula about the diagonals of Pascal's triangle.

In music Fibonacci numbers are sometimes used to determine tunings, and, as in visual art, to determine the length or size of content or formal elements.

Even more amazing is a surprising relationship to magic squares. Magic squares are arrangements of numbers in a square pattern in which all the rows, columns, and diagonals add up to the same number. The simplest is the 3x3 pattern shown below:

2	7	6
9	5	1
4	3	8

If one substitutes for these numbers the corresponding Fibonacci number, a new "magic square" is produced in which the sum of the products of the three rows is equal to the sum of the products of the three columns.

For More applications refer link:

http://library.thinkquest.org/27890/applications5.html

http://en.wikipedia.org/wiki/Fibonacci_number