Faulhaber's formula for olympiads

This is part of a series of articles based on my high school research paper from 2021 covering nonstandard approaches to solving olympiad problems. The problems from the Latvian Open Mathematics Olympiad mentioned in the article can be found in the LU NMS archive.

Faulhaber’s formula is a result which, at least in Latvian, is mentioned extremely infrequently. In fact, looking up “Faulhabera formula” on Google shows my research paper as the only result that is not machine translated.

Therefore, let’s take the opportunity to find out what it is. The formula will hand us a few very useful equations, which we will try using in olympiad problems.

The description and application of Faulhaber’s formula is fairly tricky. For your first readthrough, you’re welcome to skim or skip everything up to the summary of useful results, and return to the earlier sections afterwards.

Faulhaber’s formula

Faulhaber’s formula is the following:

If $a$ and $n$ are positive integers, then \[1^a+2^a+\ldots+n^a=\frac{1}{a+1}\sum_{j=0}^aC_{a+1}^jB_jn^{a+1-j},\] where $C_{a+1}^j=\binom{a+1}{j}$ is a combination and $B_j$ is the $j$-th Bernoulli number.

We will make no attempt to prove this result - that, in my view, would be way beyond what is expected of high school students. However, we can definitely try using the formula. To do that, we must first get to know the Bernoulli numbers.

Bernoulli numbers

Bernoulli numbers frequently appear in select scenarios from mathematical analysis, but we do not actually need to know calculus to compute them. We can use the definition \[B_j=1-\sum_{k=0}^{j-1}\frac{C_{j}^kB_k}{j-k+1}.\] It follows from this equation that the first few Bernoulli numbers are:

\begin{aligned} B_0&=1&&=\:1, \\ B_1&=1-\frac{C_{1}^0B_0}{2}&=1-\frac{1\cdot1}{2}&=\frac12, \\ B_2&=1-\frac{C_{2}^0B_0}{3}-\frac{C_{2}^1B_1}{2}&=1-\frac{1\cdot1}{3}-\frac{2\cdot\frac12}{2}&=\frac16, \\ B_3&=1-\frac{C_{3}^0B_0}{4}-\frac{C_{3}^1B_1}{3}-\frac{C_{3}^2B_2}{2}&=1-\frac{1\cdot1}{4}-\frac{3\cdot\frac12}{3}-\frac{3\cdot\frac16}{2}&=\:0. \end{aligned}

Continuing from there, we can compute even more Bernoulli numbers:

$B_0$	$B_1$	$B_2$	$B_3$	$B_4$	$B_5$	$B_6$	$B_7$	$B_8$	$B_9$	$B_{10}$	…
$0$	$\tfrac12$	$\tfrac16$	$0$	$-\tfrac1{30}$	$0$	$\tfrac1{42}$	$0$	$-\tfrac1{30}$	$0$	$\tfrac5{66}$	…

One quick observation is that $B_3=B_5=B_7=B_9=0.$ This is not a coincidence, and indeed $B_j=0$ whenever $j$ is an odd number larger than $1$.

This was a brief description of the Bernoulli numbers of the second kind, where $B_1=\tfrac12.$ The research paper used a source that assumed $B_j$ is the $j$-th Bernoulli number of the first kind, where $B_1=-\tfrac12,$ thus Faulhaber’s formula looks a little different in the paper.

Consequent equations

Once we’ve computed these Bernoulli numbers, we can choose the exponent $a$ and get very helpful equations.

Let’s try plugging in $a=1.$ We get \begin{aligned} 1+2+\ldots+n&=\frac{1}{2}\sum_{j=0}^1 C_{2}^jB_jn^{2-j} \\ &=\frac{1}{2}(C_{2}^0B_0n^2+C_{2}^1B_1n^1) \\ &=\frac{1}{2}(1\cdot1\cdot n^2+2\cdot\tfrac12\cdot n) \\ &=\frac{1}{2}(n^2+n), \end{aligned} where $n^2+n$ can be factored to get the famous equation \[1+2+\ldots+n=\frac{n(n+1)}{2}.\]

If we plug in $a=2,$ we get \begin{aligned} 1^2+2^2+\ldots+n^2&=\frac{1}{3}\sum_{j=0}^2C_{3}^jB_jn^{3-j} \\ &=\frac{1}{3}(C_{3}^0B_0n^{3}+C_{3}^1B_1n^{2}+C_{3}^2B_2n^{1}) \\ &=\frac{1}{3}(1\cdot1\cdot n^{3}+3\cdot\tfrac12\cdot n^{2}+3\cdot\tfrac16\cdot n) \\ &=\frac{1}{3}(n^{3}+\tfrac32n^{2}+\tfrac12n). \end{aligned} This expression can also be factored, which gives us the equation \[1^2+2^2+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}.\]

Let’s check out $a=3$ also. Plugging that in, we get \begin{aligned} 1^3+2^3+\ldots+n^3&=\frac{1}{4}\sum_{j=0}^3C_{4}^jB_jn^{4-j} \\ &=\frac{1}{4}(C_{4}^0B_0n^{4}+C_{4}^1B_1n^{3}+C_{4}^2B_2n^{2}+C_{4}^3B_3n^{1}) \\ &=\frac{1}{4}(1\cdot1\cdot n^{4}+4\cdot\tfrac12\cdot n^{3}+6\cdot\tfrac16\cdot n^2+4\cdot0\cdot n) \\ &=\frac{1}{4}(n^{4}+2n^{3}+n^2). \end{aligned} Factoring the last expression, we get \[1^3+2^3+\ldots+n^3=\frac{n^2(n+1)^2}{4}.\]

Summary

We can now say that, according to Faulhaber’s formula, the following three equations hold: \begin{aligned} 1+2+\ldots+n&=\frac{n(n+1)}{2}, \\ 1^2+2^2+\ldots+n^2&=\frac{n(n+1)(2n+1)}{6}, \\ 1^3+2^3+\ldots+n^3&=\frac{n^2(n+1)^2}{4}. \end{aligned} Also, we could use the formula to fairly quickly get equations involving higher exponents.

Next, we will take a look at some olympiad problems, where we will just use these equations right away. However, there is an important note to be made about the use of these equations in practice:

Since Faulhaber’s formula is not very well known, merely stating that the equation holds per Faulhaber’s formula might be insufficient. To use, say, the second equation, I would recommend first writing what exactly Faulhaber’s formula tells us, for instance, \[1^2+2^2+\ldots+n^2=\frac{1}{3}(C_{3}^0B_0n^{3}+C_{3}^1B_1n^{2}+C_{3}^2B_2n^{1}),\] and continue by manually inputting the Bernoulli numbers $B_0=1,B_1=\tfrac12,B_2=\tfrac16$ and getting the equation.

Olympiad examples

Latvian Open Mathematics Olympiad 2017/2018, Form 11, Problem 1.
Prove that, for any positive integer $n$, we have \[1^3+2^3+3^3+\ldots+n^3=(1+2+3+\ldots+n)^2.\]

Inserting the first equation derived from Faulhaber’s formula into the right hand side, we get \[(1+2+3+\ldots+n)^2=\left(\frac{n(n+1)}{2}\right)^2=\frac{n^2(n+1)^2}{4}.\] The equation in the problem follows from the third equation we got using Faulhaber’s formula.

Latvian Open Mathematics Olympiad 2018/2019, Form 10, Problem 1.
Prove that, for any positive integer $n$, we have \[6+24+60+\ldots+n(n+1)(n+2)=\frac{n(n+1)(n+2)(n+3)}{4}.\]

The left hand side can be rewritten as \[\sum_{i=1}^n i(i+1)(i+2)=\sum_{i=1}^n (i^3+3i^2+2i)=\sum_{i=1}^n i^3+3\sum_{i=1}^n i^2+2\sum_{i=1}^n i.\] Here we can insert all three of our equations to get \begin{aligned} &\sum_{i=1}^n i^3+3\sum_{i=1}^n i^2+2\sum_{i=1}^n i \\ =\,&\frac{n^2(n+1)^2}{4}+3\cdot\frac{n(n+1)(2n+1)}{6}+2\cdot\frac{n(n+1)}{2} \\ =\,&\frac{n^2(n+1)^2+2n(n+1)(2n+1)+4n(n+1)}{4} \\ =\,&\frac{n(n+1)[n(n+1)+2(2n+1)+4]}{4} \\ =\,&\frac{n(n+1)[n^2+5n+6]}{4} \\ =\,&\frac{n(n+1)(n+2)(n+3)}{4}. \\ \end{aligned}

Final thoughts

Of all ideas that appear in the research paper, I would say that Faulhaber’s formula is the most nonstandard of them all. Personally, I have never seen it mentioned in any olympiad context, perhaps because exponents higher than $a=3$ appear infrequently, and the aforementioned three equations can also be proven with a much more typical approach - induction.

Additionally, it also seems tricky to use Faulhaber’s formula in a way that graders would understand, or at least mark as fully correct.

However, knowing at least the three consequent equations is certainly useful, since you can then try using them in the problem right away. If and only if that actually leads to a solution is there a point in going through the whole ordeal of proving them.