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.
