Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I really need some help in doing this:
By using the generating functions $F(z)$ and $L(z)$ for Fibonacci and Lucas numbers, show that: $$ F_n = \frac{L_{n-1}}{2}+\frac{L_{n-2}}{2^2}+\ldots+\frac{L_0}{2^n}.$$
I have found that $F(z)=\frac{z}{1-z-z^2}$ and $L(z) = \frac{2-z}{1-z-z^2}$ but I am stuck here.
Any assistance would be helpful.
You may consider that $$ \sum_{k=0}^{n} L_{n-k}\frac{1}{2^k} $$ is a convolution product, namely the coefficient of $x^n$ in the product between $L(x)$ and $$ \sum_{n\geq 0}\frac{x^n}{2^n} = \frac{1}{1-\frac{x}{2}} = \frac{2}{2-x}. $$ By exploiting the generating functions you have found, it follows that $$ \sum_{k=0}^{n} L_{n-k}\frac{1}{2^k} = [x^n]\frac{2}{1-z-z^2}=[x^n]\left(F(z)+L(z)\right)=F_n+L_n$$ so $$ \sum_{k=1}^{n}L_{n-k}\frac{1}{2^k} = F_n+L_n-L_n = \color{red}{F_n}$$ as wanted.
