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