## Sum of the Following Series (Fibonacci & Lucas) [closed]

So i have been at this problem for the past 3 nights, and still not getting the final equation.

The problem is as follows :

F(n) : Nth term in the Fibonacci Series
F(n) = F(n-1) + F(n-2) for n>=2
0 1 1 2 3 5 8 13 21 34 55 .... Starting from Index 0
F(n) = (a^n - b^n)/√5


Also we have a Lucas Series

Luc(n) = F(n-1) + F(n+1)
L(n) = Luc(n-1) + Luc(n-2) for n>=2
2 1 3 4 7 11 18 29 47 76 ..... Starting from Index 0
Luc(n) = a^n + b^n


For a and b :

a*b = -1
a+b = 1
a-b = √5


I have to find the sum of the following series :

 n
Σ F(k)*F(n+5-k)
k=2


To solve it , i have followed this :

F(k)*F(n+5-k) = ((a^k - b^k)/√5)*((a^(n+5-k) - b^(n+5-k))/√5
= ((a^(n+5)+b^(n+5))/5) - (a^k * b^(n+5-k) + a^(n+5-k) * b^k))/5
= (Luc(n+5)/5) - (a^k * b^(n+5-k) + a^(n+5-k) * b^k)/5


Using a*b = -1

I got

F(k)*F(n+5-k) = (Luc(n+5)/5) - ((-1)^k)*(a^2k * b^(n+5) + a^(n+5) * b^2k)/5


Now

 n                                                n
Σ F(k)*F(n+5-k) = (Luc(n+5)/5)*((n*(n+1)/2)-1) - Σ((-1)^k)*(a^2k * b^(n+5) + a^(n+5) * b^2k)/5)
k=2                                              k=2


Solving the second term in the above equation i get :

        n                   n
b^(n+5) Σ(-a^2)^k + a^(n+5) Σ(-b^2)^k
k=2                 k=2


Using the sum of Geometric Series and some rearrangement I get the following :

(b^(n+1) - a^(n-3))/(a^2 + 1)   +   (a^(n+1) - b^(n-3))/(b^2 + 1)


Luc(n+3) + Luc(n+1) - Luc(n-2) - Luc(n-3)
-----------------------------------------
5


and the final series boils down to

     n
Σ F(k)*F(n+5-k) = ((Luc(n+5)/5)*((n*(n+1)/2)-1) - (Luc(n+3) + Luc(n+1) - Luc(n-2) - Luc(n-3))/5)/5
k=2


But this is not giving me the right value for a given value of n. Where am I going wrong ?

-
In the step where you add the summation, I don't see why you have a quadratic polynomial factor in $(Luc(n+5)/5)*((n*(n+1)/2)-1)$. That should be just $(Luc(n+5)/5)*(n-1)$. – Klaus Draeger Sep 7 at 11:37
Oh crap! Got it! I expanding it as (1 + 2 + 3 + 4 + .... ).. Thanks a lot! – Kyuubi Sep 7 at 12:00
This exact sum came up on math.stackexchange.com very recently - was that you, or coincidence? Anyway, that's a better site for it, as this site is for questions with a research angle. – Gerry Myerson Sep 7 at 12:47
Its a part of a very good programming question asked in a recent competition. Hence the popping up of similar questions everywhere I guess. And thank you for the link, will keep the other site in mind from next time. – Kyuubi Sep 7 at 14:52