How is Faulhaber's formula derived?

I have been wanting to understand how to find the sum of this series.

$$1^p + 2^p + 3^p +{\dots} + n^p$$

I am familiar with Gauss' diagonalised adding trick for the sum of the first $n$ natural numbers.

I can prove the formulas for

\begin{align} \sum_{1}^{n} k^2 &= \frac{n(n+1)(2n+1)}{6}\\ \sum_{1}^{n} k^3 &= \frac{n^2(n+1)^2}{4}\\ \sum_{1}^{n} k^4 &= \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} \\ \end{align}

With mathematical induction. But, beyond that even proofs with mathematical induction are difficult.

I'm interested in learning the theory and the proof behind Faulhaber's formula. What is the knowledge required to understand this proof ?

• Fulhaberg?? xDD Feb 22, 2016 at 16:00
• There's a proof on Wikipedia. Have you checked that? Feb 22, 2016 at 16:08
• Possible duplicate of Is there a general product formula for $\sum\limits_{k=1}^{n} k^p$ Feb 22, 2016 at 16:22
• The other question is the duplicate of this one, which has more detail in the question and answers. @DietrichBurde
– zyx
Feb 22, 2016 at 18:24
• Have a look here: codeproject.com/Tips/792255/Faulhaber-made-easy
– user65203
Jul 6, 2016 at 12:23

5 Answers

The following interesting derivation is from Aigner's "A Course in Enumeration" (Springer, 2007).

Remember that if we have the following exponential generating functions:

\begin{align} \widehat{A}(z) &= \sum_{n \ge 0} a_n \frac{z^n}{n!} \\ \widehat{B}(z) &= \sum_{n \ge 0} b_n \frac{z^n}{n!} \end{align}

then also:

\begin{align} \widehat{A}(z) \cdot \widehat{B}(z) &= \sum_{n \ge 0} \left( \sum_{0 \le k \le n} \frac{a_k}{k!} \frac{b_{n - k}}{(n - k)!} \right) z^n \\ &= \sum_{n \ge 0} \left( \sum_{0 \le k \le n} \frac{n!}{k! (n - k)!} a_k b_{n - k} \right) \frac{z^n}{n!} \\ &= \sum_{n \ge 0} \left( \sum_{0 \le k \le n} \binom{n}{k} a_k b_{n - k} \right) \frac{z^n}{n!} \end{align}

Let's define:

\begin{align} S_m(n) = \sum_{1 \le k \le n - 1} k^m \end{align}

We can define the exponential generating function:

\begin{align} \widehat{S}_n(z) &= \sum_{m \ge 0} S_m(n) \frac{z^m}{m!} \\ &= \sum_{1 \le k \le n - 1} \sum_{m \ge 0} \frac{k^m z^m}{m!} \\ &= \sum_{1 \le k \le n - 1} \mathrm{e}^{k z} \\ &= \frac{\mathrm{e}^{n z} - 1}{\mathrm{e}^z - 1} \\ \end{align}

This is almost the exponential generating function of the powers of $n$:

\begin{align} \widehat{P}_n(z) &= \sum_{m \ge 0} n^m \frac{z^m}{m!} \\ &= \mathrm{e}^{n z} \end{align}

We can write:

\begin{align} (\widehat{P}_n(z) - 1) \widehat{B}(z) = z \widehat{S}_n(z) \tag{1} \end{align}

where we have the exponential generating function of the Bernoulli numbers:

\begin{align} \widehat{B}(z) &= \frac{z}{\mathrm{e}^z - 1} \\ &= \sum_{n \ge 0} B_n \frac{z^n}{n!} \end{align}

Comparing coefficients of $z^{m + 1}$ in (1):

\begin{align} \sum_{m \ge 1} z^m \sum_{0 \le k \le m} \binom{m}{k} \frac{(n z)^{m - k}}{(m - k)!} B_k = \sum_{m \ge 0} S_m(n) \frac{z^{m + 1}}{m!} \end{align}

we get after simpĺifying:

\begin{align} S_m(n) = \frac{1}{m + 1} \, \sum_{0 \le k \le m} \binom{m + 1}{k} B_k n^{m + 1 - k} \end{align}

Note: The formula given is often associated with Faulhaber, but Faulhaber's formulas where quite different (and computationally more efficient). This formula is due to Bernoulli.

• Thank you for the wonderful book recommendation. I am still working through your proof and trying to understand it. Feb 26, 2016 at 4:58
• @user230452, ask if you require any clarification. I'll be happy to update the answer. Feb 26, 2016 at 11:26
• I'm working through generatingfunctionology to understand what the exponential generating function is and how you applied it here. :) Feb 26, 2016 at 12:46
• Do you know any more good books like the one you mentioned ? Feb 26, 2016 at 13:26
• @user230452, that depends on what you want. And asking for a list of "good books" is off-topic here. But you can search (I try to give references to the places where I found particularly interesting tidbits, for one). Feb 26, 2016 at 13:34

For the expression of $\sum n^k$ as a polynomial in $n$ with Bernoulli numbers in the coefficients, the background is calculus of finite differences.

For seeing why and when the linear factors $n$, $n+1$ and $2n+1$ divide the answer, the background needed is some basic algebra of polynomials. Also for showing that the sum for odd $k$ is a polynomial in $n(n+1)$.

The Wikipedia page is informative and links to an expository paper by Beardon on the same subject.

• What do I need to know and do to understand calculus of finite differences ? What are some good resources ? Feb 22, 2016 at 16:33
• Essentially no background except algebra and familiarity with polynomials. Any book with "calculus of finite differences" as its title should do. It was popular stuff in the 19th century which implies that the necessary prior knowledge is minimal by today's standards. And the old books are quite readable.
– zyx
Feb 22, 2016 at 17:43
• @user230452: Or try this: cs.purdue.edu/homes/dgleich/publications/… Feb 22, 2016 at 18:50

This probably won't take you all the way to Faulhaber's formula, but it can help you get to the closed form of $\sum_{k=1}^nk^p$ for any whole $p$.

$$\sum_{k_1=0}^{n-1}\sum_{k_2=0}^{k_0-1}\sum_{k_3=0}^{k_1-1}\dots\sum_{k_x=0}^{k_{x-1}-1}1=\frac{n(n-1)(n-2)\dots(n-x+1)}{1\times2\times3\times\dots\times x}$$

$$=\frac{n!}{x!(n-x)!}=\binom nx$$

For example,

$$\sum_{k=1}^nk^0=1+1+1+\dots+1=\sum_{k=0}^{n-1}1=n$$

$$0^1+\sum_{k=1}^nk^1=\sum_{k=0}^nk^1=\sum_{k_1=0}^{(n+1)-1}\sum_{k_2=0}^{k_1-1}1=\frac{(n+1)((n+1)-1)}2=\frac{n(n+1)}2$$

And you can keep doing this for higher values of $p$.

• could you add the next case, $\sum_k k^2$, to help better understand how you'd use this method for less trivial examples?
– glS
Oct 8, 2020 at 18:18
• @glS It is essentially this method. An example with $\sum_kk^3$ is given. Oct 10, 2020 at 13:10

An elementary proof here for $$p$$ is odd:

Let $$S_p(n) = \sum_{r=0}^n r^p$$,

Then $$2S_{p+1}(n) = \sum_{r=0}^n r^{p+1} + (n-r)^{p+1}$$

$$2S_{p+1}(n) = \sum_{r=0}^n (r^{p+1} + \sum_{i=0}^{p+1} C(p+1, i) (-1)^i r^i n^{p+1-i})$$

$$2S_{p+1}(n) = \sum_{r=0}^n (r^{p+1} + r^{p+1} + \sum_{i=0}^{p} C(p+1, i) (-1)^i r^i n^{p+1-i})$$

Fix $$n$$ and call $$S_{p+1}(n)$$ by $$S_{p+1}$$

$$2S_{p+1} = 2S_{p+1} + \sum_{r=0}^n (\sum_{i=0}^{p} C(p+1, i) (-1)^i r^i n^{p+1-i})$$

$$(\sum_{r=0}^n \sum_{i=0}^{p} C(p+1, i) (-1)^i r^i n^{p+1-i}) = 0$$

Therefore $$\sum_{i=0}^{p} C(p+1, i) (-1)^i S_i n^{p+1-i} = 0$$

and we find the formula for $$S_p$$ (which stands for $$S_p(n)$$) by the above formula.

All sums can be derived from the following induction formula:

$$\color{red}{(n+1)^p -1 =\sum_{i=0}^{p-1}\binom{p}{i} S_n(i)}$$ where we let $$S_n(p)=\sum_{k=1}^{n} k^p\qquad n, p\in\mathbb N ~~~~~\text{called Cavalieri sum of oder p}$$

Let us prove the formula We know the following Binomial formula

$$(k+1)^p = k^p+ \sum_{i=0}^{p-1}\binom{p}{i} k^i$$ where $$\binom{p}{i}= \frac{p!}{i!(p-i)!}$$. Which implies that,

$$\sum_{k=1}^{n} (k+1)^p =\sum_{k=1}^{n} k^p+\sum_{i=0}^{p-1}\binom{p}{i} \sum_{k=1}^{n} k^i = S_n(p) +\sum_{i=0}^{p-1}\binom{p}{i} S_n(i)$$

But $$\sum_{k=1}^{n} (k+1)^p = \sum_{k=2}^{n+1} k^p = S_{n+1}(p) -1 = S_n(p) +(n+1)^p -1$$

Hence finally we get the formula :

$$\color{red}{(n+1)^p -1 =\sum_{i=0}^{p-1}\binom{p}{i} S_n(i)=pS_n(p-1)+\sum_{i=0}^{p-2}\binom{p}{i} S_n(i)}.$$ It is possible to compute the sum for any $$p\ge 1$$ in $$\mathbb N$$. For instance,

• For $$p=1$$ we get $$S_n(0)= \sum_{k=1}^n 1=n.$$

• For $$p=2$$ we get $$(n+1)^2-1= S_n(0)+2 S_n(1)\implies S_n(1)= \frac12n(n+1)=\sum_{k=1}^n k$$

• For $$p=3$$ we get $$(n+1)^3-1= S_n(0)+3S_n(1)+ 3S_n(2)\\ \implies S_n(2)= \frac13((n+1)^3- (n+1)) - \frac12n(n+1)\\ S_n(2)= \frac16n(n+1)(2n-1)=\sum_{k=1}^n k^2$$