Suppose you want to know this sum for some n and k:

Here are the well known formulas for the first several k:

But suppose you forgot them. What to do? Luckily, there is an easy algorithm to generate those formulas.

First of all, let's prove a theorem.

### Theorem

Suppose for every integer non-negative n:

where f and g are polynoms. Then for some constant c:

### Proof

For every positive integer n:

These two polynoms are equal in an infinite number of points, which means that they are identical. Which allows us to say:

### Application

Let's say we want to find the formula for the sum of squares. Then using our theorem we can create such an algorithm:

Now let's run the same algorithm to find the formula for the sum of cubes:

I hope the technique has already discussed in the very beginning chapter of Knuth's Concrete Math book.

Hard version: 1677F - Tokitsukaze и драгоценные камни

Straightforward version: 1467 timus

Maybe the easier and more direct way (if you want to do it for all $$$k$$$ up to some limit) would be to notice that

But on the other hand, it's also $$$g_k(n) - g_k(n-1) = n^k$$$, hence we get the recurrence

or, for $$$g_k(n)$$$, it would be

starting with $$$g_0(n) = n$$$.

Thus,

Also I think it would be nice to write down the algorithm from the blog in generic form for arbitrary $$$k$$$:

From this, one gets

where $$$c$$$ is picked in a way that guarantees that $$$g_k(1) = 1$$$, that is

and the free constant $$$c'$$$ that would appear from integration should be $$$c'=0$$$, as $$$g_k(0)=0$$$.

Compared to the scheme I described above, it's probably beneficial for larger $$$k$$$, as it allows to find it in $$$O(k)$$$ per term, rather than $$$O(k^2)$$$. I wonder if there is a more explicit formula for $$$c$$$...