Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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



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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.