A Fibonacci convolution

Question

A Fibonacci convolution. Recall that $$F(x)=\sum_{n=0}^\infty F_n x^n =\frac{x}{1-x-x^2} =\frac{1}{\sqrt{5}} \left(\frac{1}{1-\Phi x} -\frac{1}{1-\bar{\Phi}x}\right).$$ (a) Prove that $\displaystyle \sum_{n=0}^\infty F_{n+1} x^n =\frac{1}{1-x-x^2}$.

(b) Prove that $\displaystyle \sum_{n=0}^\infty (2F_{n+1} -F_n)x^n =\frac{2-x}{1-x-x^2} =\sum_{n=0}^\infty (\Phi^n +\bar{\Phi}^n) x^n$.

(c) Prove that $\displaystyle 5F(x)^2 =\sum_{n=0}^\infty \binom{n+1}{1} \Phi^n x^n -2\sum_{n=0}^\infty F_{n+1} x^n +\sum_{n=0}^\infty \binom{n+1}{1} \bar{\Phi}^n x^n$.

(d) Prove that $\boldsymbol{\displaystyle \sum_{k=0}^n F_k F_{n-k} =\frac{2n F_{n+1} -(n+1)F_n}{5}}$.

I've gotten through (a)-(c) but I don't know how to start (d).

Answer 1

Since you have already mastered a.) to c.) we can conveniently use the results to prove d.).

We obtain \begin{align*} \color{blue}{5F(x)^2}&=\sum_{n=0}^{\infty}(n+1)\left(\Phi^n+\bar{\Phi}^n\right)x^n-2\sum_{n=0}^\infty F_{n+1}x^n\tag{1}\\ &=\sum_{n=0}^\infty(n+1)\left(2F_{n+1}-F_n\right)x^n-2\sum_{n=0}^\infty F_{n+1}x^n\tag{2}\\ &\,\,\color{blue}{=\sum_{n=0}^\infty\left(2nF_{n+1}-(n+1)F_n\right)x^n} \end{align*} and d.) follows.

Comment:

• In (1) we apply c.) by using $\binom{n+1}{1}=n+1$ and collecting the first and the last sum.

• In (2) we use from b.) the identity $2F_{n+1}-F_n=\Phi^n+\bar{\Phi}^n$.