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.
 A: 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
$$
