# Sum of product of Fibonacci numbers

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.

-
Have you tried calculating the first few examples? What did you get? Do you see a pattern? And what does this have to do with math-software? – Gerry Myerson Sep 3 '12 at 12:38
math-software is probably such a common noob tag because it is one of the first auto-suggests when you type "math" in the required tag field, and also because the people asking for math help might want to eventually use the answer to their math problem in a software. Hence math-software, the perfect combination. – binn Sep 3 '12 at 12:47
you can use the generating function $f(x)=\sum_k F_k x^k=x/(1-x-x^2)$ and notice that your numbers are the coefficients of the power series $f(x)^2$ - that will give you a recurrence relation – user8268 Sep 3 '12 at 12:47
@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. – Thomas Andrews Sep 3 '12 at 13:05

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

-
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. – Sasha Sep 3 '12 at 21:21