Sum of nth powers and generalized polynomial sum

Question

So this is a 2-part question (both parts I believe are closely related):

How exactly does on express the sum

$$\sum_{i=0}^{k}{i^n} = Q(n,k)$$

in a closed form For arbitrary positive integers $k,n$

Example:

$$Q(0,k) = k$$ $$Q(1,k) = \frac{1}{2}k(k+1)$$ $$Q(2,k) = \frac{1}{6}k(k+1)(2k+1)$$

etc...

and More generally if $P(i)$ is a polynomial. Is there a closed form for

$$\sum_{i=0}^{k}P(i)$$

Clearly if we were to decompose $P$ into its individual powers:

$$P = \sum_{i=0}^{n} a_i x^i$$ we can use the earlier formula to sum over each of these and generate a solution:

$$\sum_{i=0}^{k}P(i) =\sum_{i=0}^{n} \left( a_i *Q(i,k) \right) $$

Answer 1

This is known as the Faulhaber's formula: http://en.wikipedia.org/wiki/Faulhaber%27s_formula