Monday 17 April 2017

discrete mathematics - 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!

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...