Prove $\sum^{k}_{i=0}{F(i)} + 1 = F(k+2)$ without induction

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}$$