7
$\begingroup$

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.

  • 2
    @user8268 not quite, because he doesnt include all the terms. Closer to half the coefficients, but even then, that's wrong when $n$ is odd.2012-09-03

1 Answers 1

7

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 $

  • 0
    Evaluation of $\sum_{k=1}^{n-1} F_k F_{n+3-k}$ is mechanically the same. Try following steps in my derivation. Alternatively, use $\sum_{k=1}^{n-1} F_k F_{n+3-k} = \sum_{k=1}^{n+2} F_k F_{n+3-k} - F_{n+2}F_1 - F_{n+1} F_2 - F_{n} F_3$ and use the recurrence relations for Fibonacci numbers.2012-09-03