Faulhaber's formula

For an integer $p\ge 0$, Faulhaber's formula expresses a sum of powers as a polynomial in the upper limit:where $B_j(x)$ are the Bernoulli polynomials. The identity $B_{p+1}(x+1)-B_{p+1}(x)=(p+1)x^p$ makes the sum telescope. This is a discrete analogue of finding an antiderivative.^[ref]

For $p=1$ the result is $n(n+1)/2$; for $p=3$ it is $n^2(n+1{)}^2/4$. Although the displayed polynomial has rational coefficients, it takes integer values at nonnegative integers.

For a fixed nonnegative integer $p$, the Faulhaber polynomial $S_p(n)$ is the rational-coefficient polynomial satisfying $S_p(n)={\sum }_{k=1}^n{k}^p$ for nonnegative integers $n$. It is characterized by $S_p(0)=0$ and $S_p(n)-S_p(n-1)=n^p$.

For example, $S_2(n)=n(n+1)(2n+1)/6$ has degree three and leading coefficient $1/3$. In general the degree is $p+1$ and the leading coefficient is $1/(p+1)$, since taking a finite difference lowers the degree by one. Faulhaber's formula constructs these polynomials from the Bernoulli polynomials.