The sequence 0,1,1,2,3,5,8,... is called the Fibonacci sequence. It starts with a 0 and a 1, and then each subsequent term is the sum of the previous two terms. We write F_n to denote the nth term in the above list.

Prove that the sum of the first n terms in the Fibonacci sequence is the (n+2)th number in the sequence minus one.

Question

The sequence 0,1,1,2,3,5,8,... is called the Fibonacci sequence. It starts with a 0 and a 1, and then each subsequent term is the sum of the previous two terms. We write F_n to denote the nth term in the above list.

Prove that the sum of the first n terms in the Fibonacci sequence is the (n+2)th number in the sequence minus one.

anonymous · Answer

Use induction.

anonymous · Answer

I should have asked "Find the sum of the first n terms of the Fibonacci sequence", otherwise 99% of proofs would be answered by "Use induction". :)

anonymous · Answer

Pretty much. And even if you would have asked that the answer would probably have been: try it for several small n, figure out a pattern and prove it by induction.