Calculating the Fibonacci Sequence
Date: 11/28/96 at 04:16:17 From: Louis Suhendra Subject: 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?
Date: 12/11/96 at 21:39:10 From: Doctor Rob Subject: Re: Fibonacci sequence 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)/2 and b = (1 - Sqrt)/2, so a - b = Sqrt. According to this formula: F(3) = (a^3 - b^3)/(a - b) = a^2 + a*b + b^2 = [(1 + Sqrt)^2 + (1 + Sqrt)*(1 - Sqrt) + (1 - Sqrt)^2]/4 = [1 + 2*Sqrt + 5 + 1 - 5 + 1 - 2*Sqrt + 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 You can do the same kind of computations for any size value of n, no matter how large. Now what is the value of F(100)? And why did we choose the sequence of values of k given above? If you want to learn more, take a look at the Math Forum's FAQ on the Golden Ratio and the Fibonacci Sequence: http://mathforum.org/dr.math/faq/faq.golden.ratio.html -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum