Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to calculate the sum of product of Fibonacci number for a given $n$. That is, for given $n$, say

$$F_1 F_n + F_2 F_{n-1} + F_3 F_{n-2} + F_4 F_{n-3} + F_5 F_{n-4} + \cdots.$$

what should be my approach.

share|improve this question
3  
Have you tried calculating the first few examples? What did you get? Do you see a pattern? And what does this have to do with math-software? –  Gerry Myerson Sep 3 '12 at 12:38
    
math-software is probably such a common noob tag because it is one of the first auto-suggests when you type "math" in the required tag field, and also because the people asking for math help might want to eventually use the answer to their math problem in a software. Hence math-software, the perfect combination. –  binn Sep 3 '12 at 12:47
6  
you can use the generating function $f(x)=\sum_k F_k x^k=x/(1-x-x^2)$ and notice that your numbers are the coefficients of the power series $f(x)^2$ - that will give you a recurrence relation –  user8268 Sep 3 '12 at 12:47
2  
@user8268 not quite, because he doesnt include all the terms. Closer to half the coefficients, but even then, that's wrong when $n$ is odd. –  Thomas Andrews Sep 3 '12 at 13:05

1 Answer 1

Let's use $$ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - (-1)^n \phi^{-n} \right) $$ where $\phi$ is a Golden ratio constant $\phi = \frac{\sqrt{5}+1}{2}$. Now the sum reduces to the combination of geometric sums: $$ \begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^k - (-1)^k \phi^{-k}\right)\left(\phi^{n-k} - (-1)^{n-k} \phi^{k-n}\right) \\ &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^n - (-1)^k \phi^{n-2k} - (-1)^{n-k} \phi^{2k-n} + (-1)^n \phi^{-n} \right) \\ &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) - \frac{\phi^{n}}{5} \sum_{k=1}^{n-1} \left( -\phi^{-2}\right)^{k} - \frac{(-1)^{n}}{5} \phi^{-n} \sum_{k=1}^{n-1} \left(-\phi^2\right)^k \end{eqnarray} $$ Using the geometric sum $\sum_{k=1}^{n-1} x^k = \frac{x-x^n}{1-x}$ we get: $$\begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) + \frac{2}{5} \frac{\phi^{n-1} + (-1)^n \phi^{1-n}}{\phi + \phi^{-1}} \\ &=& \frac{n-1}{5} L_n + \frac{2}{5} F_{n-1} \end{eqnarray} $$ where $L_n$ denotes $n$-th Lucas number.

Quick sanity check in Mathematica:

In[84]:= Table[
 Sum[Fibonacci[k] Fibonacci[n - k], {k, 1, n - 1}] == (n - 1)/
    5 LucasL[n] + 2/5 Fibonacci[n - 1], {n, 1, 6}]

Out[84]= {True, True, True, True, True, True}


The sum stated in the edited question is obtained by replacing $n$ with $n+1$ in the sum evaluated above: $$ \sum_{k=1}^{n} F_k F_{n+1-k} = \frac{n}{5} L_{n+1} + \frac{2}{5} F_n $$

share|improve this answer
    
Evaluation of $\sum_{k=1}^{n-1} F_k F_{n+3-k}$ is mechanically the same. Try following steps in my derivation. Alternatively, use $\sum_{k=1}^{n-1} F_k F_{n+3-k} = \sum_{k=1}^{n+2} F_k F_{n+3-k} - F_{n+2}F_1 - F_{n+1} F_2 - F_{n} F_3$ and use the recurrence relations for Fibonacci numbers. –  Sasha Sep 3 '12 at 21:21

Your Answer

 
discard

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.