Prove Fibonacci Identity using generating functions

Question

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!

Answer 1

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.

Answer 2

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.