# How to solve an interesting first order recurrence

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.

• Try to express the sum as a third order polynomial of $n$. – user58697 Mar 25 '18 at 4:25
• The sum can be written in terms of $\sum i$ and $\sum {i^2}$, both of which have nice closed form. – Poon Levi Mar 25 '18 at 4:26
• 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}$$ – achille hui Mar 25 '18 at 18:23