Find sum $\sum _{k=0}^nF_kF_{n-k}$ 
Find sum $\sum _{k=0}^nF_kF_{n-k}$

My try
Let $$ a_n = \sum _{k=0}^nF_kF_{n-k} // \cdot x^n  
\\ a_n x^n = \sum _{k=0}^nF_k x^k F_{n-k} x^{n-k} // \sum_n \\
A(x) = (F(x))^2 + \cdots + (F(x))^2 = n\cdot (F(x))^2$$
I have some doubts:

*

*I am not sure that summing $F_k x^k$ by $n$ gives $F(x)$ (generating functions for $f_n$ sequence)

*If it is true, how can it be finished? There is weird situation. I know that $a_n$ is a element from $\sum _{k \ge 0} F_k \cdot \sum _{k \ge 0} F_k$ multiplied by $n$ but it is not obvious for me how it can be extracted from there.

 A: Hint: Convolution of sequences corresponds to the multiplication of their generating functions.
The generating function of Fibonacci sequence is $$F(z) = (\frac{1}{\sqrt5})(\frac{1}{1-\phi z} - \frac{1}{1-\hat{\phi} z})$$
Thus, we need the coefficient of $z^n$ in $F^2(z)$
$F^2(z) = \frac{1}{5}(\frac{1}{(1-\phi z)^2} + \frac{1}{(1-\hat{\phi} z)^2}-\frac{2}{(1-\phi z)(1-\hat{\phi}z)})$
$F^2(z) =\frac{1}{5}(\Sigma_{n\ge 0}(n+1)\phi^n z^n - 2\Sigma_{n\ge 0}f_{n+1} z^n+\Sigma_{n\ge 0}(n+1)\hat{\phi}^n z^n)$
$F^2(z) =\frac{1}{5}(\Sigma_{n\ge 0}(n+1)(2f_{n+1} - f_{n})z^n - 2\Sigma_{n\ge 0}f_{n+1}z^n)$
$\therefore \sum _{k=0}^nf_kf_{n-k} = \frac{2nf_{n+1} - (n+1)f_{n}}{5}$
A: I guessed the formula, then prove it by induction.
Let $s_n = \sum_0^n F_k F_{n-k}$
From identity: $F_m F_n = F_m F_{n+1} + F_{m-1} F_n$ 
$s_n = (n-1) F_{n-1} - s_{n-2}$
$s_n = (n-1) F_{n-1} - (n-3) F_{n-3} + (n-5) F_{n-5} - \cdots$
Simplify the sum, so that $s_n = a F_{n} + b F_{n-1}$, and build a table:
$$\begin{matrix}
n & s_n & a & b \cr
2 & 1 & 1/5 & 4/5 \cr
3 & 2 & 2/5 & 6/5 \cr 
4 & 5 & 3/5 & 8/5 \cr
5 & 10 & 4/5 & 10/5 \cr
6 & 20 & 5/5 & 12/5
\end{matrix}$$
Guessed formula for $s_n = \frac{(n-1)F_n + 2 n F_{n-1}}{5}$
The prove is in pairs, check n=1,2; assumed true for n=k; check n=k+2:
For n=1, $\frac{(1-1)(1) + (2)(1)(0)}{5} = 0$
For n=2, $\frac{(2-1)(1) + (2)(2)(1)}{5} = 1 = F_1^2$ 
For n=k+2, use recurrence formula to build $s_{k+2}$:
$$(k+1)F_{k+1} - \frac{(k-1)F_k + 2 k F_{k-1}}{5} = \frac{((k+2)-1)F_{k+2} + 2 (k+2) F_{(k+2)-1}}{5}$$
QED 
