Calculating the Fibonacci Sequence

Is there a formula that can be used to calculate the nth Fibonacci 

number?

For example, if we want to know the 100th Fibonacci number, do we have 

to count one by one?

The answer to the first question is, "Yes, but ..."  The answer to the

second question is, "No."  Now for the explanations!  Sorry they are

so long.

The standard formula for the Fibonacci numbers is due to a French

mathematician named Binet.  If F(n) represents the nth Fibonacci 

number, then:

      F(n) = (a^n - b^n)/(a - b)

where a and b are the two roots of the quadratic equation x^2-x-1 = 0.

It is not obvious how to derive this formula, but it is easy to prove 

that it satisfies F(0) = 0, F(1) = 1, and satisfies the same recursion 

as the Fibonacci numbers do.  We can use the quadratic formula to see 

that a = (1 + Sqrt[5])/2 and b = (1 - Sqrt[5])/2, so a - b = Sqrt[5].  

According to this formula:

      F(3) = (a^3 - b^3)/(a - b)

           = a^2 + a*b + b^2

           = [(1 + Sqrt[5])^2 + (1 + Sqrt[5])*(1 - Sqrt[5]) +

               (1 - Sqrt[5])^2]/4

           = [1 + 2*Sqrt[5] + 5 + 1 - 5 + 1 - 2*Sqrt[5] + 5]/4

           = 8/4

           = 2

You might not guess that the formula always produces an integer for 

each value of n, but such is the case.

Unfortunately, computing with this formula is not very easy!  Luckily,

there is another way.  We use the recursion F(n+1) = F(n) + F(n-1) and 

the starting values F(0) = 0, F(1) = 1.  We also use an auxiliary 

sequence called the Lucas numbers, which we will denote by L(n).  They 

are defined by L(0) = 2, L(1) = 1, and L(n+1) = L(n) + L(n-1).  Their 

Binet formula is:

      L(n) = a^n + b^n

with the same a and b as before.  We need the following formulas, too:

      F(n+1) = [F(n) + L(n)]/2

      L(n+1) = [5*F(n) + L(n)]/2

We also use the following "doubling formulas":

      F(2*n) = F(n)*L(n),

      L(2*n) = L(n)^2 - 2(-1)^n

We compute in sequence the pairs (F[k], L[k]) for k = 0, 1, 2, 3, 6, 

12, 24, 25, 50, and 100:

   k   F(k) L(k)

   0   0    2

   1   1    1

   2   1    3

   3   2    4

   6   8    18

   12  144  322

    and so on.

Not slf-rittn bt slf-edited,fnd it interestng hop sm of ur ques r ansrd.

Hope u lyk it guys!!!!!