Sums of powers


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.

Read the rest of this entry »