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!

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.
