Sum of Fibonacci Series

Date: 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/