I would like to know to simplify the summation given in the problem SANBAN
ie) Σi*fibonacci(i)
LINK : Banta needs help
In this question, if you observe and calculate initial terms , you can get a simple formulae to
solve your problem.
The formulae for the problem is (n-1)*fib(n+2)-fib(n+1)+2.
and you can calculate nth fibonacci number using matrix exponentiation in O(logN) time which will pass both the subtasks,here’s the link
https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/. It is a great blog for understanding matrix exponentiation.
I hope this clears your problem! 
1 Like
First let us find out the sum of the first n Fibonacci numbers.
\begin{aligned}
f(n) &= f(n+2) - f(n+1) \\
f(n-1) &= f(n+1) - f(n) \\
f(n-2) &= f(n) - f(n-1) \\
...&=\;... \\
f(2) &= f(4) - f(3) \\
f(1) &= f(3) - f(2) \\
\sum_{i=1}^n f(i) &= f(n+2) - f(2)
\end{aligned}
Now we are ready to solve the given problem.
\begin{aligned}
n \times f(n) &= n\times (f(n+2) - f(n+1)) \\
(n-1) \times f(n-1) &= (n-1) \times (f(n+1) - f(n)) \\
(n-2) \times f(n-2) &= (n-2) \times (f(n) - f(n-1)) \\
..... &= \;..... \\
2 \times f(2) &= 2 \times (f(4) - f(3)) \\
1 \times f(1) &= 1 \times (f(3) - f(2)) \\
\therefore \sum_{i=1}^n i \times f(i) &= n \times f(n+2) - \{f(n+1) + f(n) + ... f(3)\} - f(2) \\
&= n \times f(n+2) - \Big\{\sum_{i=1}^{n+1}f(i) - f(2) - f(1)\Big\} - f(2) \\
&= n \times f(n+2) - \sum_{i=1}^{n+1}f(i) + f(1) \\
&= n \times f(n+2) - f(n+3) + f(2) + f(1) \\
\sum_{i=1}^n i \times f(i) &= n \times f(n+2) - f(n+3) + 2
\end{aligned}
That is the final form which can be used to solve the problem. Here is my code for reference, using matrix exponentiation for calculation of the Fibonacci numbers : link.
Cheers!
2 Likes
@meooow , can you help me here - https://discuss.codechef.com/questions/98844/can-anyone-explain-the-problem-geometric-trick