500th Fibonacci NumberDate: 04/16/97 at 12:16:29 From: Dung Che Che Subject: Fibonacci numbers Dear Dr. Math, I was hoping you could help me figure out an extra credit math problem. My calculus teacher has challenged us to find the 500th term of the Fibonacci sequence. In high school, I figured out the 100th term by adding on my calculator, but this seems to be more of a challenge. So if you could maybe give me a formula and some instructions, I would greatly appreciate it. Thank you for your time. Date: 04/18/97 at 10:39:43 From: Doctor Rob Subject: Re: Fibonacci numbers This is quite challenging, since the answer has 105 decimal digits! There are two ways to proceed. (1) Use Binet's formula for the Fibonacci numbers, drop the small term, and round. Fibonacci numbers are defined by F(0) = 0, F(1) = 1, and (F) F(n+1) = F(n) + F(n-1) for n > 1. Binet's formula says that: F(n) = (a^n - b^n)/(a - b) where a = (1 + Sqrt[5])/2 b = (1 - Sqrt[5])/2 Observe that a - b = Sqrt[5], a + b = 1, and a*b = -1. You can actually prove that this formula is correct by showing that F(0) = (a^0 - b^0)/(a - b), F(1) = (a^1 - b^1)/(a - b), and that (a^n - b^n)/(a - b) satisfies the same recursion that F(n) does. Then apply the principle of mathematical induction to conclude that the Binet formula holds for all nonnegative n. This may seem impossible, but all of the Sqrt[5] terms evaporate when the formula is expanded, and the result is, in fact, an integer. Furthermore, since -1 < b < 0, it turns out that |b^n/Sqrt[5]| < 1/2 for all nonnegative n, so it is true that: F(n) ~=~ a^n/Sqrt[5] If you can compute the quantity on the right to 110 significant figures, then rounding it off to the nearest integer will give your answer. (2) Use the doubling formulas for Fibonacci and Lucas numbers. Lucas numbers are defined as follows: L(0) = 2, L(1) = 1, and (L) L(n+1) = L(n) + L(n-1) for n > 1 There is also a Binet formula for them: L(n) = (a^n + b^n)/(a + b) a and b are the same as defined above. Since a + b = 1, we could write L(n) = a^n + b^n. You can also prove this formula using mathematical induction. Fibonacci and Lucas numbers satisfy the following identities, which you can prove using the principle of mathematical induction, or directly using the Binet Formulas: (A) F(2*n) = F(n)*L(n) (B) L(2*n) = L(n)^2 - 2*(-1)^n (C) F(n+1) = (F(n) + L(n))/2 (D) L(n+1) = (5*F(n) + L(n))/2 (L') L(n) = L(n+1) - L(n-1) To compute F(500), use (A) and the values of F(250) and L(250). To compute F(250), use (A) and the values of F(125) and L(125). To compute L(250), use (B) and the value of L(125). To compute F(125), use (C) and the values of F(124) and L(124). To compute L(125), use (D) and the values of F(124) and L(124). To compute F(124), use (A) and the values of F(62) and L(62). To compute L(124), use (B) and the value of L(62). To compute F(62), use (A) and the values of F(31) and L(31). To compute L(62), use (B) and the value of L(31). To compute F(31), use (C) and the values of F(30) and L(30). To compute L(31), use (D) and the values of F(30) and L(30). To compute F(30), use (A) and the values of F(15) and L(15). To compute L(30), use (B) and the value of L(15). To compute F(15), use (C) and the values of F(14) and L(14). To compute L(15), use (D) and the values of F(14) and L(14). To compute F(14), use (A) and the values of F(7) and L(7). To compute L(14), use (B) and the value of L(7). To compute F(7), use (C) and the values of F(6) and L(6). To compute L(7), use (D) and the values of F(6) and L(6). To compute F(6), use (A) and the values of F(3) and L(3). To compute L(6), use (B) and the value of L(3). You can compute directly that F(3) = 2, L(3) = 4. Now work your way back up the chain above, computing F(n) and L(n) for n = 6, 7, 14, 15, 30, 31, 62, 124, 125, and 250, then F(500). As a check, F(500) starts off 13942... and ends ...94125. Alternatively, since you already know F(100), you could compute L(n) using (B) for the even n's and (L') for the odd n's in the sequence n = 2, 3, 4, 6, 8, 7, 12, 14, 13, 24, 26, 25, 50, and 100. Then use the additional identity (E) F(5*n) = F(n)*[L(n)^4 - 3*(-1)^n*L(n)^2 + 1] with n = 100. You can prove this directly from the Binet formulae. Good question! -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/