# Reducing this expression to simpler form

$\newcommand{\Fib}{\operatorname{Fib}}$I am trying to reduce this expression for the $n$th term of sequence $G$.

$G[n]=\Fib(4) \times \Fib(n-1) + \Fib(5) \times \Fib(n-2) + \Fib(6) \times \Fib(n-3)+ \cdots +\Fib(n+3) \times \Fib(1)$

Here $\Fib()$ is the Fibonacci sequence $1,2,3,5,8,13, \ldots$

How can I simplify expression for $G[n]$?

I have read the various identities given on Wikipedia but have not been able to apply them. Any help will be highly appreciated, as I have been stuck on this for two days.

-
possible duplicate of Summation of series of product of Fibonacci numbers –  Brian M. Scott Sep 3 '12 at 21:40
See Robert Israel’s answer to the question cited above. –  Brian M. Scott Sep 3 '12 at 21:41
@BrianM.Scott:Sir I don't consider it as an exact duplicate .Here I would like to add that I need a formula that doesn't require any floating point computation. –  thedarkknight Sep 3 '12 at 21:49
If you don't want to use floating point, you are stuck with a recursion formula you have to evaluate step by step after manually computing $G(1)), G(2), G(3), G(4)$: $G(n) = 2G(n-1)+G(n-2)-2G(n-3)-G(n-4)$ –  Hagen von Eitzen Sep 3 '12 at 22:07

Using the usual indexing of the Fibonacci numbers, $F_0=0,F_1=1$, etc., you want

$$G(n)=\sum_{k=2}^nF_kF_{n+3-k}\;.$$

Now

\begin{align*} G(n)-G(n-2)&=\sum_{k=2}^nF_kF_{n+3-k}-\sum_{k=2}^{n-2}F_kF_{n+1-k}\\ &=F_nF_3+F_{n-1}F_4+\sum_{k=2}^{n-2}F_kF_{n+2-k}\\ &=F_nF_3+F_{n-1}F_4-F_{n-1}F_3+\sum_{k=2}^{n-1}F_kF_{n+2-k}\\ &=2F_n+F_{n-1}+G(n-1)\\ &=F_{n+2}+G(n-1)\;, \end{align*}

so $$G(n)=G(n-1)+G(n-2)+F_{n+2}\;.\tag{1}$$

$(1)$ allows easy recursive calculation of the $G$ and Fibonacci numbers in parallel using only integer arithmetic, starting with $G(2)=2,G(3)=7,F_5=5$, and $F_6=8$. Alternatively, you can avoid the Fibonacci numbers altogether and use the fourth-order recurrence given by Hagen in the comments. You won’t be able to find a closed form using only integer arithmetic.

-