Sum of Fibonacci SeriesDate: 05/23/2000 at 04:40:14 From: Edward Barton Subject: Fibonacci sequence Is there any formula for the sum of the first n numbers in the Fibonacci sequence? I've been looking for one without success. I did find a quartic equation that worked for the first few (five or six), but it got progressively more inaccurate. I have also tried plotting them against the respective terms of the Fibonacci sequence, which almost gave a straight line, but it was not quite close enough. Date: 05/23/2000 at 05:36:14 From: Doctor Mitteldorf Subject: Re: Fibonacci sequence Dear Edward, Believe it or not, the Fibonacci series is the sum of two geometric series, each one of which separately is not even an integer. Given the formula, it's not too hard to prove that it works (use proof by induction). But where does the formula come from? The formula involves the square root of 5, which I write as sqrt[5]. The nth Fibonacci is: a*x^n + (1-a)*y^n where a = (3+sqrt[5])/(5+sqrt[5]) x = (1+ sqrt[5])/2 y = (1- sqrt[5])/2 So my challenges to you are: first, to prove that the formula works, and second, to derive the equation you want for the sum of the first n terms, using the formula for the sum of a geometric series. Read more about Fibonacci series at our FAQ page at: Golden Ratio, Fibonacci Sequence http://mathforum.org/dr.math/faq/faq.golden.ratio.html - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ Date: 05/23/2000 at 05:51:52 From: Doctor Floor Subject: Re: Fibonacci sequence Hi, Edward, Thanks for writing. We know that the nth Fibonacci number F(n) = (PHI^n - (1 - PHI)^n) / sqrt[5] where PHI = (1+sqrt[5])/2 = 'Golden ratio' See, for instance, "Fibonacci Formula Inductive Proof" from the Dr. Math archives: http://mathforum.org/dr.math/problems/joly11.5.97.html I will use the value of F(0) in my sum of the first n Fibonacci numbers. That doesn't matter because F(0) = 0. So we can derive the following: SUM{i = 0 to n} F(n) = SUM{i = 0 to n} (PHI^i - (1 - PHI)^i) / sqrt5 = (1/sqrt5)*{[SUM{i = 0 to n} PHI^i] - [SUM{j = 0 to n} (1-PHI)^j]} Using the formula for a geometric series we know: SUM{i = 0 to n} PHI^i = (PHI^(n+1)-1)/(PHI - 1) and SUM{j = 0 to n} (1-PHI)^j = ((1-PHI)^(n+1) - 1)/-PHI so we conclude: (1/sqrt[5])*{[SUM{i = 0 to n} PHI^i] - [SUM{j = 0 to n} (1-PHI)^j]} ( PHI^(n+1) - 1 (1-PHI)^(n+1) - 1 ) 1 = ( ------------- + ----------------- )* ------- ( PHI-1 PHI ) sqrt[5] PHI^(n+2) - PHI - (1-PHI)^(n+2) - PHI + 1 = ----------------------------------------- [use PHI*(PHI-1) = 1] sqrt5*PHI*(PHI-1) PHI^(n+2) - (1-PHI)^(n+2) 1 - 2*PHI = ------------------------- + --------- sqrt[5] sqrt[5] = F(n+2) - 1 We see that there comes a very simple formula {F(0) +} F(1) + F(2) + ... + F(n) = F(n+2) - 1 _^^^^^^^^_ not needed Now that we found the formula, it seems that you can prove it more easily by mathematical induction. Try it! If you need more help, just write back. Best regards, - Doctor Floor, The Math Forum 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/