Prove Fibonacci Identity using generating functions I have the following summation identity for the Fibonacci sequence.
$$\sum_{i=0}^{n}F_i=F_{n+2}-1$$
I have already proven the relation by induction, but I also need to prove it using generating functions, but I'm not entirely sure how to approach it.
I do know that the generating function for the fibonacci sequence is $$F(x) = \dfrac{1}{1-x-x^2}$$
But, I'm not entirely sure if that applies here.  Any help would be appreciated!
 A: Since a generating function for the Fibonacci numbers $(F_n)_{n\geq 0}=(1,1,2,3,5,8,\ldots)$ is
\begin{align*}
\frac{1}{1-x-x^2}=1+x+2x^2+3x^3+5x^4+8x^5+\cdots
\end{align*}
and multiplication of a generating function $A(x)$ with $\frac{1}{1-x}$ results in summing up the coeffcients
\begin{align*}
\frac{1}{1-x}A(x)&=\frac{1}{1-x}\sum_{n=0}^\infty a_nx^n\\
&=\sum_{n=0}^\infty\left(\sum_{i=0}^n a_i\right)x^n
\end{align*}

we can show the following:
  \begin{align*}
\sum_{i=0}^n F_i=F_{n+2}-1\qquad\qquad n\geq 0\tag{1}
\end{align*}
A generating series of the LHS of (1) is
  \begin{align*}
\sum_{n=0}^\infty\left(\sum_{i=0}^n F_i\right)x^n=\frac{1}{1-x}\cdot\frac{1}{1-x-x^2}
\end{align*}
A generating series of the RHS of (1) is
  \begin{align*}
\sum_{n=0}^\infty \left(F_{n+2}-1\right)x^n&=\sum_{n=0}^\infty F_{n+2}x^n-\sum_{n=0}^\infty x^n\\
&=\sum_{n=2}^\infty F_n x^{n-2}-\frac{1}{1-x}\tag{2}\\
&=\frac{1}{x^2}\left(\frac{1}{1-x-x^2}-1-x\right)-\frac{1}{1-x}\tag{3}\\
&=\frac{1}{(1-x)(1-x-x^2)}\\
\end{align*}
  and the claim follows.

Comment:


*

*In (2) we shift the index $n$ by two to start from $n=2$ and use the formula for the geometric series expansion.

*In (3) we use the generating function series of the Fibonacci numbers and do some simplifications in the line after.
A: Another interesting prove for sum of Fibonacci numbers is by matrix method. suppose that 
$$
S^{(j)}=\sum_{i=0}^j\,f_i
$$
where $f_i$ is the $i$th term of Fibonacci numbers. Now, consider the following matrix
$$
M= 
\left( \begin {array}{ccc}
 1&0&0\\ 
 0&0&1\\ 
 1&1&1
\end {array} \right)
$$
With the induction on $n$ you can prove that the $n$th power of matrix $M$ is as follows 
$$
M^n= 
\left( \begin {array}{ccc}
 1&0&0\\ 
 S^{(n-1)}&f_{n-1}&f_n\\ 
 S^{(n)}&f_n&f_{n+1}
\end {array} \right)
$$
By using the first column of the relation $M^n=M\, M^{n-1}$, we have
$$
\left( \begin {array}{c}
 1\\ 
 S^{(n-1)}\\ 
 S^{(n)}
\end {array} \right)=
\left( \begin {array}{ccc}
 1&0&0\\ 
 0&0&1\\ 
 1&1&1
\end {array} \right)\, 
\left( \begin {array}{c}
 1\\ 
 S^{(n-2)}\\ 
 S^{(n-1)}
\end {array} \right)
$$
The last row of the above matrix equation, results that
$$
1+ S^{(n-2)}+S^{(n-1)}=S^{(n)}
$$
From definition of $S^{(j)}$, we obtain the following relation
$$
S^{(n)}=f_n+S^{(n-1)}
$$
From the last two equation, we conclude that
$$
1+S^{(n-2)}=f_n \Longrightarrow f_0+f_1+\cdots +f_{n-2}=f_n-1
$$ 
By this method, we can obtain interesting relations between generalized Fibonacci numbers.  
