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.

What is the sum of following product of Fibonacci numbers

$$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$

can anyone suggest only approach to find general term?

share|improve this question
    
In the usual numbering, $fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3$ –  Robert Israel Sep 3 '12 at 18:29
    
My first thought is Binet's + geometric sum formula. –  anon Sep 3 '12 at 18:41
2  
You have post a very similar question, and haven't commented or accepted the answer. At least, you should referenced that question here. math.stackexchange.com/questions/190443/… –  leonbloy Sep 3 '12 at 18:42
1  
Rahul, if you don't get the answer you want on a question, you edit the question. You don't post a rehash of the old question. –  Gerry Myerson Sep 3 '12 at 23:56
    
@GerryMyerson ok thanks I will take care of that from next time onward –  Rahul Kumar Dubey Sep 4 '12 at 13:41

2 Answers 2

Assuming you're using the usual numbering of the Fibonacci numbers, the Binet equation $$\text{fib}(n) = \frac{\phi^n - (-1/\phi)^n}{\sqrt{5}}$$ where $\phi = (1 + \sqrt{5})/2$ implies your sum is $$ F(n) = \left((2 + \sqrt{5}) \frac{n}{5} - \frac{7 \sqrt{5}}{25}\right) \phi^n + \left((2 - \sqrt{5}) \frac{n}{5} + \frac{7 \sqrt{5}}{25}\right) (-1/\phi)^n $$ The first few terms ($n = 1$ to $10$) are $0, 3, 8, 19, 40, 80, 154, 289, 532, 965$.

EDIT: It seems your $\text{Fib}(n) = \text{fib}(n+1)$. So your sum is $$\sum_{k=1}^{n-1} \text{fib}(k+1) \text{fib}(n+4-k) = \left(\frac{\sqrt {5} n}{2}+{\frac {11 n}{10}}-{\frac {21}{50}}\sqrt {5}-\frac{3}{2} \right) \phi^n + \left(-\frac{\sqrt {5} n}{2}+{\frac {11 n}{10}}+{\frac {21}{50}}\sqrt {5}-\frac{3}{2} \right) (-1/\phi)^n $$ The first few terms ($n=1$ to $10$) are $0, 5, 18, 44, 96, 195, 380, 719, 1332, 2428$. The generating function is $$g(t) = {\frac {t \left( 3\,t+5 \right) \left( t+1 \right) }{ \left( {t}^{2}+ t-1 \right) ^{2}}} $$

share|improve this answer
1  
could you please explain how to find the generating function? –  ajay Sep 7 '12 at 7:34
    
Geometric series and its derivative. –  Robert Israel Sep 7 '12 at 15:43

It is also possible to compute function values one at a time by using the recursion formula $G(n) = 2G(n-1)+G(n-2)-2G(n-3)-G(n-4)$ after manually computing the first four values. (The validity of the formula follows e.g. with Robort Israel's explicit formula and the defining identity for $\phi$; note that $x^4-(2x^3+x^2-2x-1)=(x^2-x-1)^2$).

share|improve this answer
    
I get $\begin{pmatrix}2 & 1 & -2 & -1\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{pmatrix}\cdot \begin{pmatrix}96\\44\\18\\5\end{pmatrix}=\begin{pmatrix}195\\96\\44\\18\end{pmatrix}$‌​, so what doyou think is wrong? –  Hagen von Eitzen Sep 4 '12 at 5:34

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.