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

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

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 ?

share|cite|improve this question
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
up vote 6 down vote accepted

Since there are a number of questions very similar to this one, I will answer a more general question which should answer most of them.

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} $$

share|cite|improve this answer
Exactly what i was looking for. This is really very neat and detailed and easy to understand. Thank you. – Arjun Datta Sep 6 '12 at 14:37

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.