# Induction Proof for the Sum of the First n Fibonacci Numbers

I'm trying to prove that there exists a formula for the sum of the first n Fibonacci numbers, using induction.

$$\sum_{i=1}^{n} F_i$$

For my class, we have denoted the recursive definition of the Fibonacci sequence as:

For n $$\in \mathbb{Z}, n> 2,$$ $$F_{n+1} = F_n + F_{n-1}$$

To try to see a formula I wrote out a table of the first n Fibonacci numbers as well as the respective partial sums through n = 9. I noticed that the pattern seemed to arise that:

$$\sum_{i=1}^{n} F_i = F_{n+2} -1$$

At this point I assumed I should begin my induction proof, since I had a conjecture to work around.

For the base case $$n=1$$:

$$\sum_{i=1}^1 F_i = 1$$ $$F_3 - 1 = 2 - 1 = 1$$

So the base case held. Then I used the induction hypothesis that the formulation would hold for an arbitrary positive integer $$k$$.

$$\sum_{i=1}^{k} F_i = F_{k+2} -1$$

Then I sought to prove that this formulation would hold for $$k+1$$ in accordance with the induction axiom.

I wanted to show that $$\sum_{i=1}^{k+1} F_i = F_{(k+1)+2} -1$$

$$\sum_{i=1}^{k+1} F_i = \left(\sum_{i=1}^{k} F_i\right) + F_{k+1}$$

$$= F_{k+2} -1 + F_{k+1} = F_{k+3} -1 = F_{(k+1) +2} -1$$ which was what I wanted.

Having proven the base case and induction step, have I proven that this formula holds true for all $$n\geq1$$? That is, am I right to assume that the formula I deduced from the first 9 Fibonacci numbers will hold true for the first $$n$$ numbers, just because I proved the induction steps? To me, that doesn't feel complete, so I'm not sure if what I've done is fully right or sufficiently rigorous.

• This is all fine. It is standard to look at at examples to form a conjecture and then prove the conjecture by induction. From a logical point of view, it doesn't matter how you found the conjecture. All that matters is that you have a valid inductive proof as you do in you example. Well done! Commented Feb 6 at 21:44
• "Having proven the base case and induction step, have I proven that this formula holds true? " Of course! That's how proofs by induction work. "am I right to assume that the formula I deduced from the first 9 Fibonacci numbers will hold true for the first n numbers, just because I proved the induction steps?" If formula were not correct you would not have been able to prove the induction step! I can unstanding that just guessing a formula might not seem valid but if you guessed a wrong one you wouldn't have been able to prove the induction steps. But since you could its right. Commented Feb 6 at 21:48
• Everything is fine like both comments above state, but I have just one small detail to point out: you've shown that the formula holds for every $n \geqslant 1$ and not just for $n > 2$.
– xyz
Commented Feb 6 at 21:50
• @xyz oh yep, you're right. I edited the typo. Commented Feb 6 at 21:51
• There is also an explicit formula for the Fibonacci numbers: Binet's formula. Commented Feb 6 at 22:26

$$\sum_0^n F_n=F_{n+2} -1$$
in agreement with your result. On that web site the definition of $$F=\{0,1,1,2,3,5,8,...\}$$.