Reducing this expression to simpler form

Question

$\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 03 '12 at 21:40
@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 03 '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 03 '12 at 22:07

score 1 · Answer 1 · answered Sep 03 '12 at 22:53

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.

Reducing this expression to simpler form

1 Answers1

Linked