How to solve an interesting first order recurrence

Question

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.

Answer 1

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.