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:

Proof

For every positive integer n: