# How to reduce the complexity of calculating the following summation? [duplicate]

Possible Duplicate:
Summation of series of product of Fibonacci numbers

Find $$\sum_{i=1}^{N-1}F_{i + 1} F_{N + 4 - i}$$

Is there a direct formula to calculate this, rather than actually sum all the terms?

EDIT: My initial summation was incorrect. Updated now.

-

## marked as duplicate by Brian M. Scott, William, Ross Millikan, Sasha, t.b.Sep 12 '12 at 20:49

Sasha’s answer to this very similar question may also be useful. – Brian M. Scott Sep 8 '12 at 0:36
Both the questions are a bit different. I also saw a similar question here. What I am looking for is a solution like the one in that link (in terms of Lucas or Fibonacci numbers) but for the slightly different summation I have put in the question. – AncientEgypt Sep 8 '12 at 1:12
The questions are substantially similar. Just take the answer to one, subtract one term, and you have the answer to this one. Please provide some motivation for why you need such a trivial variation? – Erick Wong Sep 8 '12 at 2:00
You need a higher reputation in order to add comments to posts that you aren't attached to. – Erick Wong Sep 8 '12 at 2:02

We seem to have a lot of "Sum of Products of Fibonacci Numbers" that are similar to each other, differing only in the limits of summation and the common total of the indices. To another question, I give a general answer that should cover all cases.

Applying $(5)$ from that answer to this question, yields \begin{align} \sum_{i=1}^{n-1}F_{i+1}F_{n+4-i} &=\sum_{i=2}^nF_iF_{n+5-i}\\ &=\frac{n-1}{5}(F_{n+4}+F_{n+6})+\frac15(F_{n-4}-F_{n+2}) \end{align}

-

I got the following formula $$\sum_{i=1}^{N-1} F_i \cdot F_{N+4-i} = \frac{11}{5} (N-1)F_N+\frac{7}{5} N F_{N-1}$$ by plugging in $F_n = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)$ and simplifying the obtained expression.

(Update: I answered the original question of OP, not the new one.)

-
you answer doesn't seem right. It doesn't give integral solutions. – AncientEgypt Sep 8 '12 at 1:56
@AncientEgypt, here are the first values that my formula gives: 0, 5, 13, 31, 65, 130, 250, 469, 863, 1565, 2805, 4980, 8772, 15349, 26705, 46235, 79705, 136886, 234302, 399845, 680515, 1155385, 1957293, 3309096, 5584200, 9407525, 15823765, 26577559, 44579633, 74681770. All of them are integers. If you think that my formula is incorrect, please, let me know for what $N$ it gives an incorrect answer. – Yury Sep 9 '12 at 2:53