0
$\begingroup$

$\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.

  • 0
    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)$2012-09-03

1 Answers 1

1

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.