Sum of the n Fibonacci numbers?

[Peppers]

What is the sum of the first n Fibonacci numbers? Use the Fiboncci numbers below to make a conjecture, and then prove it using mathematical induction.

 

[b]n     [i]tn[/i][/b]
1     1
2     1
3     2
4     3
5     5
6     8
7     13
8     21
9     34
10    55
11    89
12    144
13    233
14    377
15    610
16    987
17    1597
18    2584
19    4181
20    6765
.....

 

I know that each Fibonacci number is the sum of the previous two, but I am unsure of how to do the question above. Could someone please show me?

[Dave]

Perhaps writing down the Fibonacci numbers next to the sum would help. Just stare at it; after a while it should leap out.

[Peppers]

I've been staring for quite awhile Please tell if you know the answer, because I still haven't got it, and I need it for an assignment.

[mezarashi]

I guess you will be happy to know that there exists a formula in which you may calculate the sum of the Fibonacci numbers knowing only "n". This formula derivation however requires some extensive analysis using some auxilary equations and is not particularly easy, so don't give up! It may or may not be within your current mathematical level, but given that this was a problem given to you I guess it should be. This neat formula was actually credited to a French mathematician Binet in the 18th century, and it quotes:

 

 

http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

[Dave]

Okay, so let's look at some numbers; F_n is the n'th fibonacci number, S_n is the sum of the first n numbers; i.e. [imath]S_n = \sum_{k=1}^{n} F_k[/imath].

 

n    1  2  3  4  5  6  7  8  9  10
F_n  1  1  2  3  5  8  13 21 34 55
S_n  1  2  4  7  12 20 33 54 ...

 

Whilst I would quite like to give you the answer straight away, we do have a policy of not giving out explicit answers unless you show a significant amount of working. I will, however, say this: observe what happens when we add 1 to the [imath]S_n[/imath]'s:

 

n      1  2  3  4  5  6  7  8  9  10
F_n    1  1  2  3  5  8  13 21 34 55
S_n+1  2  3  5  8  13 21 34 55 ...

 

The way I've written it should give the obvious corellation between [imath]S_n + 1[/imath] and [imath]F_{n+2}[/imath]. From there, it's fairly trivial to prove using induction.

[Dave]

I should probably add that once you have proved your conjecture, it's a fairly simple affair to get a formula explicitly in terms of n, using the Binet formula for F_n, as mezarashi has given it.

[Peppers]

Ah, I see, that Binet formula would have helped me, unfortunately i didnt get a chance to go on the internet until today. Thanks for all of your help anyways.

On the bright side, i found the sum of the terms on my own yesturday, after looking at the numbers for ever!

I got (sigma notation from i=1 to n) t(n + 2) -1

and then i proved tru with mathematical induction

 

PS. how do you do those mathematical symbols on the forums (i had to write "sigma notation" and the "t(n + 2)" means the nth + 2 term in the series)

[Dave]

Have a look at the "LaTeX Quick Start" thread in the General Maths forum (it's stickied).