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

Question

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.

Answer 1

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

Answer 2

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