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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.