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.
• The MathJax is not clear. What does $// \cdot$ mean? – Peter Foreman Aug 18 at 14:23
• multiplying both sides by – Tester1998 Aug 18 at 14:24
• Generally $//$ means that I am do something for both sides – Tester1998 Aug 18 at 14:24
• If that's the case, what does $//\sum_{n}$ mean? That most certainly is abuse of notation. – Don Thousand Aug 18 at 14:31
• Consider $F(x)^2.$ – Lord Shark the Unknown Aug 18 at 14:52

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}$$

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