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$ Commented Sep 3, 2012 at 18:29
  • $\begingroup$ My first thought is Binet's + geometric sum formula. $\endgroup$
    – anon
    Commented 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
    Commented 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$ Commented Sep 3, 2012 at 23:56
  • $\begingroup$ @GerryMyerson ok thanks I will take care of that from next time onward $\endgroup$ Commented 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
    Commented Sep 7, 2012 at 7:34
  • $\begingroup$ Geometric series and its derivative. $\endgroup$ Commented 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$ Commented Sep 4, 2012 at 5:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .