Parker Glynn-Adey | Faulhaber Polynomials

This is an outline of a talk or workshop that I'd like to present. It is somewhat terse. Consider it a work in progress. Feedback welcome.

Faulhaber polynomials calculate the following sum: \[ f(p, n) = 1^p + 2^p + \dots + n^p = \sum_{x=1}^n x^p. \] Various formulae for small values of $p$ were known in antiquity. For example, \[ f(0,n) = n \quad \quad f(1,n) = \frac{n(n+1)}{2} \quad \quad f(3,n) = \frac{n(n+1)(2n+1)}{6}. \] In the early 1600s, Johann Faulhaber extended this list, giving explicit polynomials for to $f(p,n)$ up to $p = 17$. Don Knuth¹ suggests that Faulhaber even had explicit forumalae up to $p = 25$. In this note, we give a simple method of finding the polynomials $f(p,n)$ using the calculus of finite differences.

First, we need to state a few facts about finite differences. Given a sequence $f : \mathbb{N} \to \mathbb{R}$ we can form its difference: \[ \Delta f(n) = f(n+1) - f(n). \] This sequence is analgous to the derivative of function because it measure the rate of change of successive terms in the sequence. More importantly, the difference satisfies an analogue of the fundamental theorem of calculus: If $f : \mathbb{N} \to \mathbb{R}$ is a sequence, then \[ \sum_{x=a}^{b} \Delta f(x) = f(b+1) - f(a). \] The proof is straightforward. When we apply the definition of the difference, we obtain a telescoping sum. All but the first and last terms cancel out. As an equation, the proof is:

\[ \sum_{x=a}^{b} \Delta f(x) = \sum_{x=a}^{b} [f(x+1) - f(x)] = f(b+1) - f(a). \] Our plan for evaluating $\displaystyle f(p,n) = \sum_{x=1}^n x^p$ is to re-write the summand $x^p$ as a difference and then apply the fundamental theorem of calculus. We now introduce a family of sequences which will helpful in carrying out this plan. The falling factorial functions are defined to be: \[ x^{\underline{n}} = x(x-1)\cdots(x - (n-1)) = \prod_{k=0}^{n-1} (x - k). \] It is convenient to define $x^{\underline{0}} = 1$. The falling factorials satisfy a factorial-like identity $x^{\underline{k}}(x-k) = x^{\underline{k+1}}$ which we will use later. Moreover, they behave like regular monomials when we take their differences: $ \Delta x^{\underline{n}} = nx^{\underline{n-1}} $. The proof is a direct calculation. We write the difference and then factor out the $n-1$ terms shared by both products. \[ \begin{array}{rcl} \Delta x^{\underline{n}} & = & (x+1)^{\underline{n}} - x^{\underline{n}} \\ & = & (x+1){(x) \cdots (x - (n-2))} \\ & & - {x(x-1) \cdots (x - (n-2))}(x - (n-1)) \\ & = & (x+1 - (x - (n-1))) [x(x-1) \cdots (x - (n-2))] \\ & = & n x^{\underline{n-1}} \end{array} \] With these preliminaries in place, we have all the tools we need to evaluate $f(p,n)$. We begin by recoving the cases known since antiquity (and the beginning of this note). The identity $f(0,n) = n$ says that $1 + \cdots + 1 = n$. Let’s derive this via the fundamental theorem of calculus. First, we recall the convention that $x^{\underline{0}}=1$. We also have that $\Delta(x^{\underline{1}}) = 1x^{\underline{0}} = 1$. This gives the following computation. \[ f(0,n) = \sum_{x=1}^n 1 = \sum_{x=1}^n x^{\underline{0}} = \sum_{x=1}^n \Delta( x^{\underline{1}} ) = (n+1)^{\underline{1}} - (1)^{\underline{1}} = n \] The method works on the simplest possible case. Let’s proceed to check the next simplest case: the sum of the naturals. \[ f(1,n) = \sum_{x=1}^n x = \frac{n(n+1)}{2} \] For this case, we need to write $x$ as a difference. To do so, we need to find an analogue of the antiderivative of $x$. The identity $\Delta(x^{\underline{2}}) = 2x^{\underline{1}}$ gives us: \[ \Delta \left( \frac{1}{2} x^{\underline{2}} \right) = \frac{1}{2} (2x^{\underline{1}}) = x^{\underline{1}} = x. \] We can now calculate, \[ f(1,n) = \sum_{x=1}^n x = \sum_{x=1}^n \Delta\left( \frac{1}{2} x^{\underline{2}} \right) = \frac{(n+1)^{\underline{2}} - 1^{\underline{2}}}{2} \] We now apply the definition of the falling factorial to obtain a formula for $f(1,n)$. We use the fact that $1^{\underline{n}} = 0$ for $n \geq 2$. \[ f(1,n) = \frac{(n+1)^{\underline{2}} - 1^{\underline{2}}}{2} = \frac{(n+1)((n+1)-1) - 0}{2} = \frac{n(n+1)}{2} \] Last, we confirm the identity for the sums of squares. \[ f(3,n) = \sum_{x=1}^{n} x^3 = \frac{n(n+1)(2n+1)}{6} \] The plan is exactly the same as before: express the summand as a difference and apply the fundamental theorem of calculus. Unlike the last two cases, we will need think a bit to rewrite $x^2$ in terms of the falling factorials. A bit of highschool algebra saves the day. \[ x^2 = x(x-1) + x = x^{\underline{2}} + x^{\underline{1}} \] Now that we have expressed $x^2$ in terms of falling factorials, we derive the formula for $f(2,n)$. As before, we find a difference equal to the summand and then apply the fundamental theorem of calculus.

\[ \begin{array}{rcl} {\displaystyle \sum_{x = 1}^n x^2} & = & \displaystyle \sum_{x = 1}^n x^{\underline{2}} + x^{\underline{1}} \\ & = & \displaystyle \sum_{x = 1}^n \Delta \left( \frac{1}{3} x^{\underline{3}} + \frac{1}{2} x^{\underline{2}} \right)\\ & = & \displaystyle \left( \frac{1}{3} (n+1)^{\underline{3}} + \frac{1}{2} (n+1)^{\underline{2}} \right) - \left( \frac{1}{3} (1)^{\underline{3}} + \frac{1}{2} (1)^{\underline{2}} \right) \\ & = & \displaystyle \frac{1}{3} (n+1)n(n-1) + \frac{1}{2} (n+1)n - 0 \\ & = & \displaystyle \frac{1}{6} (n+1)n \left[ 2(n-1) + 3 \right] \\ & = & \displaystyle \frac{n(n+1)(2n+1)}{6} \end{array} \] The last few steps are an algebraic grind. We’ve now confirmed the classical formulae for $f(p,n)$ where $n \leq 3$. To finish off this note, we’ll explain how to extend this list using a bit of algebra.

Suppose that we had a polynomial for $x^{p-1}$ in terms of falling factorials. We can extend this to a polynomial for $x^p$ by using the falling factorial identity $x^{\underline{k}}(x-k) = x^{\underline{k+1}}$. We calculate.

\[ \begin{array}{rcl} {\displaystyle x^p} = x^{p-1}x & = & \displaystyle \left( \sum_{k=0}^{p-1} a_k x^{\underline{k}}\right)x \\ & = & \displaystyle \sum_{k=0}^{p-1} a_k x^{\underline{k}}x \\ & = & \displaystyle \sum_{k=0}^{p-1} a_k x^{\underline{k}} ((x - k) + k) \\ & = & \displaystyle \sum_{k=0}^{p-1} a_k x^{\underline{k+1}} + k a_k x^{\underline{k}} \end{array} \]

This gives recursive relationship between the coefficients for $x^{p}$ and those of $x^{p-1}$. If we write the coefficient of $x^{\underline{k}}$ in the expression of $x^p$ as $a_k(p)$ we get: $a_{k}(p) = ka_k(p-1) + a_{k-1}(p-1)$. To start the recursion, we use the values from $x = x^{\underline{1}}$, which are: $a_0(1) = 0$, $a_1(1) = 1$, and $a_k(1) = 0$ for $k \geq 2$.

Knuth, Donald E. “Johann Faulhaber and Sums of Powers.” Mathematics of Computation, vol. 61, no. 203, 1993, pp. 277–94. JSTOR, https://doi.org/10.2307/2152953. Accessed 24 May 2025. ↩︎

Tags:

Backlinks:

Navigation Menu:

Thanks for reading! If you have any comments or questions about the content, please let me know. Anyone can contact me by email.