Sum of Powers

Given , the function

is a polynomial of degree given by

where we used these notations: Stirling Number of the Second Kind Binomial Coefficient

Proof

Use the identity from Stirling Number of the Second Kind to change basis of the vector space of polynomials of degree from to

Now just calculate:

The last sum is done using a Binomial Coefficient identity.