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!
No comments:
Post a Comment