Answer to nth fibonacci number

We have the recursion formula for fibonacci series as
               f(n)=f(n-1)+f(n-2)

We can derive a formula for the function as
 f(n) - f(n-1) - f(n-2) = 0
which is transformed into a recurrence relation problem as..
x^2 - x - 1=0
The solution is  x= (1 + 5)/2 and x=(1- 5)/2.
therefore the homogenius solution is
        .

1 + √5

n

+A2

1 – √5

n

f(n) =

A1

2

2

 Since the initial condition is
     f(0)=0
     f(1)=1
Therefore A1 + A2 =0
               A1*((1 + 5)/2) + A2*((1 - 5)/2) = 1
solving the above two equations ,
A1=(1/5) and A2=(-1/5).

ie. the formula for f(n)=

1

1 + √5

n

–

1 – √5

n

√5

2

2

This formula is called
I present a simple python program to implement this..

import math
a=math.sqrt(5)
p=(1+a)/2
q=(1-a)/2
n=raw_input("enter the number n  : ")
n=int(n)
print int((p**n-q**n)/a)