# Summation Of Product Of Fibonacci Numbers

Im trying to find out a general term for the following summation of products of fibonacci numbers:--

# $$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$

I tried using Binet's equation but I am getting stuck at a certain point. So, I would be very glad if someone could post an answer to my question with a detailed explanation.

Here are the first few values of the summation for different values of n :--
n = 3 , ans = 9
n = 4 , ans = 30
n = 5 , ans = 73
n = 6 , ans = 158

Note : I have used the usual fibonacci notation. i.e
$$F_0=0,\;F_1=1,\;F_2=1,\;F_3=2,\;...etc$$

EDIT
After reading the comments for this question I tried solving it to form a recurrence relation and this is what i ended up with :--

\begin{align*} G(n)&=\sum_{k=4}^{n+1} F_kF_{n+5-k}\; , n \geq 3\\ G(n)-G(n-1)&=\sum_{k=4}^{n+1} F_kF_{n+5-k}-\sum_{k=4}^{n} F_kF_{n+4-k}\\ &=F_{n+1}F_{4}+\sum_{k=4}^{n}F_kF_{n+3-k}\\ &=F_{n+1}F_{4}+F_{n}F_{3}+\sum_{k=4}^{n-1}F_kF_{n+3-k}\\ \\ &=F_{n+1}F_{4}+F_{n}F_{3}+G(n-2)\\ \\ G(n)&=G(n-1)+G(n-2)+F_{n+1}F_{4}+F_{n}F_{3}\\ \\ \end{align*}

Is this correct ? And how do I reduce it further ?

-
– Hagen von Eitzen Sep 5 '12 at 20:13
You are clearly getting $3F(n+1)$, but I don't have a proof. – Byron Schmuland Sep 5 '12 at 20:23
@ByronSchmuland Then use of generating function should nail it. – Sasha Sep 5 '12 at 20:24
Letting $a_n$ denote the sum in question you can show $a_n = a_{n-1} + a_{n-2} + F_{n+4}$ where $F_k$ is the $k$-th Fibonacci number. Maybe this helps. – Cocopuffs Sep 5 '12 at 20:50
@HagenvonEitzen : Thanks for pointing out those links. I checked them and tried to solve it according to one of those methods. I edited the question with my results. However, I got stuck after a certain point. Please do check it out and help me to complete it. – Arjun Datta Sep 6 '12 at 2:52

Using the closed form for the Fibonacci numbers, $$F_n=\frac{\phi^n-(-1/\phi)^n}{\sqrt{5}}\tag{1}$$ and Lucas numbers $$L_n=\phi^n+(-1/\phi)^n\tag{2}$$ we get \begin{align} F_iF_{n-i} &=\frac{\phi^i-(-1/\phi)^i}{\sqrt{5}}\frac{\phi^{n-i}-(-1/\phi)^{n-i}}{\sqrt{5}}\\ &=\frac{\phi^n+(-1/\phi)^n-(-1)^i\left(\phi^{n-2i}+(-1/\phi)^{n-2i}\right)}{5}\\ &=\frac{L_{n}-(-1)^iL_{n-2i}}{5}\tag{3} \end{align} To sum Lucas numbers, we use $(2)$ and the formula for the sum of a geometric series: \begin{align} \sum_{i=j}^{k-1}F_iF_{n-i} &=\sum_{i=j}^{k-1}\frac{L_{n+5}-(-1)^iL_{n-2i}}{5}\\ &=\color{#C00000}{\frac{k-j}{5}L_{n}}\\ &\color{#00A000}{-\frac15\sum_{i=j}^{k-1}\phi^{n}\left(-1/\phi^2\right)^i}\\ &\color{#0000FF}{-\frac15\sum_{i=j}^{k-1}(-1/\phi)^{n}\left(-\phi^2\right)^i}\\ &=\color{#C00000}{\frac{k-j}{5}L_{n}}\\ &\color{#00A000}{-\frac{\phi^{n}}{5}\frac{\left(-1/\phi^2\right)^k-\left(-1/\phi^2\right)^j}{\left(-1/\phi^2\right)-1}}\\ &\color{#0000FF}{-\frac{(-1/\phi)^{n}}{5}\frac{\left(-\phi^2\right)^k-\left(-\phi^2\right)^j}{\left(-\phi^2\right)-1}}\\ &=\color{#C00000}{\frac{k-j}{5}L_{n}}\\ &\color{#00A000}{+\frac15\frac{-(-1)^{n-k}(-1/\phi)^{2k-n-1}-(-1)^{j}\phi^{n-2j+1}}{\phi+1/\phi}}\\ &\color{#0000FF}{+\frac15\frac{+(-1)^{n-k}\phi^{2k-n-1}+(-1)^{j}(-1/\phi)^{n-2j+1}}{\phi+1/\phi}}\\ &=\frac{k-j}{5}L_{n}+\frac15\left((-1)^{n-k}F_{2k-n-1}-(-1)^jF_{n-2j+1}\right)\tag{4}\\ &=\frac{k-j}{5}(F_{n-1}+F_{n+1})+\frac15\left((-1)^{n-k}F_{2k-n-1}-(-1)^jF_{n-2j+1}\right)\tag{5} \end{align}
Applying $(4)$ to the current problem yields $$\sum_{k=4}^{n+1}F_kF_{n+5-k}=\frac{n-2}{5}(F_{n+6}+F_{n+4})-\frac25F_{n-2}\tag{5}$$