5
$\begingroup$

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 $

EDIT
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 ?

  • 0
    @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.2012-09-06

1 Answers 1

6

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

  • 0
    Exactly what i was looking for. This is really very neat and detailed and easy to understand. Thank you.2012-09-06