## Sums of powers

15/03/2016

When you’re studying algorithms, there is a number of series and expression that keep showing up. A while ago, I discussed the special form $\sum_{i=1}^n i a^i$. But that’s not the only one. Another form that keeps showing up is

$\displaystyle s_k(n)=\sum_{i=1}^n i^k$.

We can look the particular form this sum takes for specific $k$ in some compendium (like CRC’s tables and formulae, that have seen 30-something editions over the last half century), or… you can find the formula yourself. It’s a bit tedious, but not that complicated.