1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ In the usual numbering, $fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3$ $\endgroup$ Sep 3, 2012 at 18:29
  • $\begingroup$ My first thought is Binet's + geometric sum formula. $\endgroup$
    – anon
    Sep 3, 2012 at 18:41
  • 2
    $\begingroup$ 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/… $\endgroup$
    – leonbloy
    Sep 3, 2012 at 18:42
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 3, 2012 at 23:56
  • $\begingroup$ @GerryMyerson ok thanks I will take care of that from next time onward $\endgroup$ Sep 4, 2012 at 13:41

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ could you please explain how to find the generating function? $\endgroup$
    – ajay
    Sep 7, 2012 at 7:34
  • $\begingroup$ Geometric series and its derivative. $\endgroup$ Sep 7, 2012 at 15:43
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Sep 4, 2012 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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