[Math] Sum of product of Fibonacci numbers

fibonacci-numberssequences-and-series

I want to calculate the sum of product of Fibonacci number for a given $n$. That is, for given $n$, say

$$F_1 F_n + F_2 F_{n-1} + F_3 F_{n-2} + F_4 F_{n-3} + F_5 F_{n-4} + \cdots.$$

what should be my approach.

Best Answer

Let's use $$ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - (-1)^n \phi^{-n} \right) $$ where $\phi$ is a Golden ratio constant $\phi = \frac{\sqrt{5}+1}{2}$. Now the sum reduces to the combination of geometric sums: $$ \begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^k - (-1)^k \phi^{-k}\right)\left(\phi^{n-k} - (-1)^{n-k} \phi^{k-n}\right) \\ &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^n - (-1)^k \phi^{n-2k} - (-1)^{n-k} \phi^{2k-n} + (-1)^n \phi^{-n} \right) \\ &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) - \frac{\phi^{n}}{5} \sum_{k=1}^{n-1} \left( -\phi^{-2}\right)^{k} - \frac{(-1)^{n}}{5} \phi^{-n} \sum_{k=1}^{n-1} \left(-\phi^2\right)^k \end{eqnarray} $$ Using the geometric sum $\sum_{k=1}^{n-1} x^k = \frac{x-x^n}{1-x}$ we get: $$\begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) + \frac{2}{5} \frac{\phi^{n-1} + (-1)^n \phi^{1-n}}{\phi + \phi^{-1}} \\ &=& \frac{n-1}{5} L_n + \frac{2}{5} F_{n-1} \end{eqnarray} $$ where $L_n$ denotes $n$-th Lucas number.

Quick sanity check in Mathematica:

In[84]:= Table[
 Sum[Fibonacci[k] Fibonacci[n - k], {k, 1, n - 1}] == (n - 1)/
    5 LucasL[n] + 2/5 Fibonacci[n - 1], {n, 1, 6}]

Out[84]= {True, True, True, True, True, True}

The sum stated in the edited question is obtained by replacing $n$ with $n+1$ in the sum evaluated above: $$ \sum_{k=1}^{n} F_k F_{n+1-k} = \frac{n}{5} L_{n+1} + \frac{2}{5} F_n $$

Related Question