Prove $\sum^{k}_{i=0}{F(i)} + 1 = F(k+2)$ without induction I want to prove that $\sum^{k}_{i=0}{F(i)} + 1 = F(k+2)$, where $F(0) = 0$, $F(1) = 1$ and for all $n \geq 2$, $F(n) = F(n-1) + F(n-2)$ without using induction.
I want to prove it without induction because I want to implement the equation within another induction proof about Fibonacci numbers. Having 2 induction proofs together would be messy.
 A: Since you're trying to prove infinitely many statements, we either use induction or properties of the objects we're working with (in this case Fibonacci numbers).  Hence, here is a proof using the latter.  You may find it unsatisfying, but there aren't that many alternatives here.

We take as given the following two identities:
$$\sum_{i=0}^{n-1} F_{2i+1}=F_{2n}$$
and
$$\sum_{i=1}^n F_{2i}=F_{2n+1}-1$$
We add the two identities  to get $$\sum_{i=1}^{2n}F_i=F_{2n}+F_{2n+1}-1=F_{2n+2}-1$$
Then we add $1$ to both sides, to get the desired identity for even $k$.  To get it for odd $k$, we replace the second identity by $\sum_{i=1}^{n-1}F_{2i}=F_{2n-1}-1$, and proceed similarly.
A: Define the matrix 
$$M=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$$
It's easy to see that the lower right hand entry of $M^n$ will have the same recurrence as the Fibonacci number.  Checking the first few will show that $F(n) = M^{n+1}_{2,2}$.  Similarly we can figure out for all the entries and see that
$$M^{n+1}=\begin{bmatrix}F(n+2) & F(n+1) \\ F(n+1) & F(n)\end{bmatrix}$$
We can write $F(n)=v^TM^{n+1}v$ for $v=[0\,\,1]^T$.
Now the sum can be writen as
$$S=\sum_{i=0}^kF(i)+1=\left(\sum_{i=0}^kv^TM^{i+1}v\right)+v^TIv=\sum_{i=0}^{k+1}v^TM^{i}v=v^T\left(\sum_{i=0}^{k+1}M^{i}\right)v$$
Now we simplify the polynomial in $M$ by noting that $M^{k+2}-I = (M-I)(\sum_{i=0}^{k+1}M^{i})$
$$S=v^T\left((M-I)^{-1}(M^{k+2}-I)\right)v$$
$$=v^T\left(\begin{bmatrix}0 & 1 \\1 & -1\end{bmatrix}^{-1}(M^{k+2}-I)\right)v$$
$$=v^T\left(M(M^{k+2}-I)\right)v$$
$$=v^T\left(M^{k+3}-M)\right)v$$
$$=v^TM^{k+3}v-v^TMv$$
$$=F(k+2)-F(0)$$
as desired.
A: Use the general term formula: $$F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}, \ \ \text{where} \ \ \phi=\frac{1+\sqrt{5}}{2}, \ \ \psi=\frac{1-\sqrt{5}}{2}.$$
Use the sum of geometric progression:
$$\begin{align}\sum^{n}_{i=0}{F(i)} + 1 &= \frac{\phi^0-\psi^0}{\sqrt{5}}+\frac{\phi^1-\psi^1}{\sqrt{5}}+\cdots + \frac{\phi^n-\psi^n}{\sqrt{5}}+1=\\
&=\frac{1}{\sqrt{5}}([\phi^1+\phi^2+\cdots +\phi^n]-[\psi^1+\psi^2+\cdots +\psi^n])+1=\\
&=\frac{1}{\sqrt{5}}\cdot \left(\frac{\phi(\phi^n-1)}{\phi-1}-\frac{\psi(\psi^n-1)}{\psi-1}\right)+1=\\
&=\frac{1}{\sqrt{5}}\cdot \left(\frac{\phi(\phi^n-1)}{-\psi}-\frac{\psi(\psi^n-1)}{-\phi}\right)+1=\\
&=\frac{1}{\sqrt{5}}\cdot \frac{\phi^2(\phi^n-1)-\psi^2(\psi^n-1)}{-\psi\cdot \phi}+1=\\
&=\frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}+ \frac{-\phi^2+\psi^2}{\sqrt{5}}+1=\\
&=\frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}=\\
&=F(n+2).\end{align}$$
