1
$\begingroup$

I want to find a general formula for calculating:

$$\sum_{i=1}^n i F_i $$

where $F_n$ is the n-th Fibonacci number. What I have done so far is: $$\sum_{i=1}^n \sum_{j=i+1}^n F_j$$

I tried to solve it using above double summation formula but it doesn't give the correct result

$F_1$ = 1, $F_2$ = 2, $F_3$ = 3, $F_4$ = 5.

(for e.g. summation upto 12 is 3916, upto 5 is 46)

$\endgroup$
  • $\begingroup$ all your indexes are wrong/bad $\endgroup$ – Exodd Apr 29 '17 at 12:21
  • $\begingroup$ Use mathworld.wolfram.com/BinetsFibonacciNumberFormula.html and gmatclub.com/forum/… $\endgroup$ – lab bhattacharjee Apr 29 '17 at 12:21
  • $\begingroup$ As @Exodd has said, for the first formula: $\sum_{i=1}^n \color{red}{i} F_{ \color{red}{i}}$ $\endgroup$ – Jean Marie Apr 29 '17 at 12:22
  • $\begingroup$ @labbhattacharjee It's way easier than that. Jordan's way to compute them is correct and leads to a close form $\endgroup$ – Exodd Apr 29 '17 at 12:23
  • $\begingroup$ sorry, I have changed the indexes $\endgroup$ – Jordan Smith Apr 29 '17 at 12:26
1
$\begingroup$

If you want to compute the sum $$\sum_{i=1}^n iF_i$$ you can write $$\sum_{i=1}^n iF_i =\sum_{i=1}^n \sum_{j=1}^i F_i = \sum_{j=1}^n \sum_{i=j}^n F_i $$ and switching $i,j$ it leads to $$ \sum_{i=1}^n \sum_{j=i}^n F_j$$ If you want to achieve a close form, you may remember $$F_1+F_2+F_3+\dots+F_k = F_{k+2}-2$$ so $$ \sum_{i=1}^n \sum_{j=i}^n F_j = \sum_{i=1}^n (F_{n+2}-2 -\sum_{j=1}^{i-1} F_j ) = nF_{n+2} - 2n - \sum_{i=1}^n(F_{i+1}-2) $$ $$= nF_{n+2} - F_{n+3}+2+F_1 =nF_{n+2} - F_{n+3} + 3 $$

$\endgroup$
  • $\begingroup$ The inner summation is $F_(n+2)$ - $F_(i+2)$, how do i go about solving the outer summation? $\endgroup$ – Jordan Smith Apr 29 '17 at 12:36
0
$\begingroup$

Using finite differences:

Let $f(n) = \sum_{i=1}^{n} iF_i$

$\Delta f(n) = (n+1)F_{n+1} = \Delta (nF_{n+2} - F_{n+3})$

$\implies f(n) = nF_{n+2} - F_{n+3} + c$

For $n=1$, $f(1) = F_1 = 1 = F_3 - F_4 + c \implies c = 3$

Hence $f(n) = nF_{n+2} - F_{n+3} + 3 $

$\endgroup$

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.