1
$\begingroup$

I was solving some programming exercises then i stumbled upon one that involved the summation of $1, 2, 3, ..., n$. But in the problem i needed to come up with a way to sum all of the instances of such sum up to some number k, that is, find:

$\sum_{i=1}^k S(i)$ , where $S(i) := \frac{i(i+1)}{2}$

So naturaly i found the recurrence relation:

$F(n) := F(n-1) + \frac{n(n+1)}{2}$, where $F(1) = 1$

But the problem is i have very little experience on solving recurrences. So I´d be glad to hear a suggestion on how to tackle it maybe just a completely different than solving the recurrence.

$\endgroup$
  • $\begingroup$ Try to express the sum as a third order polynomial of $n$. $\endgroup$ – user58697 Mar 25 '18 at 4:25
  • $\begingroup$ The sum can be written in terms of $\sum i$ and $\sum {i^2}$, both of which have nice closed form. $\endgroup$ – Poon Levi Mar 25 '18 at 4:26
  • 1
    $\begingroup$ There is no need to solve any recurrence. You are dealing with a telescoping sum! $$\frac{i(i+1)}{2} = \frac{(i+2)-(i-1)} {3}\cdot\frac{i(i+1)}{2} = \frac{i(i+1)(i+2)}{6} - \frac{(i-1)i(i+1)}{6} $$ $\endgroup$ – achille hui Mar 25 '18 at 18:23
1
$\begingroup$

Hint:

  • Faulhaber's formula is often referred in this case. Two instances are \begin{align*} \sum_{i=1}^k i=\frac{k(k+1)}{2}\qquad\qquad \sum_{i=1}^k i^2=\frac{k(k+1)(2k+1)}{6} \end{align*}

  • See for instance this MSE answer for a method how to derive such formulas.

$\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.