The Sum of Powers —New Equations and A Unique Derivation of Faulhaber’s Formula
1¹²+2¹²+3¹²+4¹²+5¹²+ · · · + n¹²= ?
I am going to give what I will call an elementary demonstration. But elementary does not mean easy to understand. Elementary means that very little is required to know ahead of time in order to understand it, except to have an infinite amount of intelligence. There may be a large number of steps that are hard to follow, but each does not require already knowing Calculus or Fourier transforms. — Richard P. Feynman
In this article I will derive Faulhaber’s Formula in a unique but elementary way (no generating functions). In addition, I will introduce an entirely new way to calculate the sums of integer powers using basic Calculus.
If you’re not familiar with Faulhaber’s Formula I suggest you read the Introduction, otherwise feel free to skip it. Feel free to skip reading any specific derivation.
Introduction
Finding formulas for the sums of integer powers has been of interest to mathematicians since antiquity. Formulas for the sum of the integers (1+2+3+···+n), squares (1²+2²+3²···+n²), and cubes (1³+2³+3³+···+n³) were known for a very long time.
But it wasn’t until the 17th century (mostly thanks to Faulhaber and Bernoulli) that a general solution was found for any integer power. This general solution is known as Faulhaber’s Formula and yields a polymomial function that depends only on n and the power p.
The well-known derivation of Faulhaber’s Formula is through the use of so-called “generating functions.” A disadvantage of this approach is that it doesn’t rely on elementary methods.
The unique derivation I will present may not be easy to understand but does rely on elementary methods: Mostly Algebra and some basic Calculus.
1 — A First and Natural Appproach
A first attempt at finding a general solution to this problem would naturally be to find formulas for higher and higher powers to try and spot a general pattern. The first one is the easiest:
Then here are the formulas for S₁ and S₂:
I challenge you to find formulas for S₃ and higher for yourself.
A general pattern you might notice is that it seems that Sₚ(n) can always be expressed as a (p+1)-th degree polynomial. It also seems that the first coefficient is always 1/(p+1). This is great but it’s no proof. Furthermore, most of the other coefficients remain mysterious. A better approach is needed.
2- Solution Using Telescoping Series
There is a relatively simple method to generate any Sₚ(n) using a concept known as “telescoping” (you will soon understand what this means).
We will first derive a polynomial expression for S₂(n) by applying a binomial expansion to (i -1)³:
Now let’s sum over (i -1)³ to get:
Note that here I replaced summing over i² with S₂ and the same for i¹ and i⁰.
Now here’s where the magic of telescoping happens. Let us subtract the sum over i³ from the sum over (i- 1)³ and work it out:
Notice how every term cancels out out except for n³.
In general this is what a telescoping series basically is: A series where every term cancels out in the sum leaving only the initial and final terms.
Now we can re-write Eq. 2.2 to get:
By re-arranging a few terms we finally get:
If you work this out you indeed get the correct polynomial expression for S₂ as given in Eq. 1.3.
We can generalize this entire process to generate any Sₚ:
Let’s define p=k-1 (as proven useful in the example for determining S₂, where the power k was equal to 3).
Then let us determine the first two terms of the sum to get:
Then by summing over everything from i=0 to n and some re-arranging we finally get:
This is a general, recursive formula for calculating any Sₚ. A major downside of this method is however that it’s very inefficient; it requires you to calculate all the previous Sₚ’s.
But this method nonetheless gives us a structure to work with and allows us to further study the properties of Sₚ. Eq. 2.9 will help us derive Faulhauber’s Formula and also a new and more efficient recursive formula for Sₚ.
3- Bernoulli Numbers and The Structure of Faulhauber’s Formula
As you have seen the family of polynomials Sₚ(n) has a recursive property. The power of Faulhaber’s formula is that it directly generates all the coefficients of Sₚ(n) without recursivity. It does this by using the relation that all the coefficients can be expressed in terms of so-called Bernoulli Numbers.
Bernoulli numbers are a set of rational numbers and they themselves have a recursive property and can be defined recursively (although modern definitions are often based on generating functions). This set of numbers is very important in mathematics and appears in the Euler–Maclaurin Formula and certain expressions of the Riemann Zeta Function.
The Bernoulli numbers are named after the mathematician Jakob Bernoulli who first discovered them. They were also discovered independently, around the same time, by the mathematician Seki Takakazu.
These numbers first appeared in the polynomial expressions for Sₚ(n) as the final coefficient, that is, the coefficient before n. So using our previous results we find that the first few values for Bₚ are B₀=1, B₁=1/2, B₂=1/6.
Now let us start by writing down such a structure (also using the structure from Eq. 2.9):
This formula has the same structure as Faulhaber’s Formula. But the coefficients still need to be made explicit. The notation will be explained further in the next section.
4 —Analysis of the Coefficients of Sₚ(n)
These coefficients of the polynomials are functions of p (subscript) and indexed from 0 to p (superscript). Here are some of the properties of these coefficients:
Now we will use our results so far to derive a recursive expression for the coefficients a(j,p).
Let us begin by analyzing Eq. 3.1.
A way to isolate specific coefficients is by differentiation and then setting n = 0. Take a look at Eq. 3.1 when written out:
Notice that when we take the derivative of S with respect to n, we get:
Now when we set n equal to zero, we are left only with the last term a(p,p)/(p+1). We can generalize this method to obtain any coefficient. E.g. if we take the second-derivative of S with respect to n, and then set n equal to zero, we obtain (2! times a(p-1, p))/(p+1). (Work this out for yourself to test that this is true!). Notice the factorial appears after repeated differentiatio n.
And in general, if we take the j-th derivative of S with respect to n and set n equal to zero, we obtain (j! times a(p-j+1, p))/(p+1):
Working this out yields the relation:
We can work out a useful expression for the coefficients by applying the same analysis on our previously derived recursive formula (Eq. 2.9):
Working this out we get:
And by using Eq 3.1 and using the summation index t instead of i (becaused i is already in use) we get:
Now let’s work out that derivative. It might look a bit tricky but if you first work out the first derivative, then the second, and so on, you will find:
Note that the equation above always yields zero except when p+2-i-t-j = 0, which is only the case when t = p+2-i-j. This means that the only non-zero value it yields is j! (when you substitute t and work out the algebra).
Combining this result with Eq. 4.9 we get:
Substituting this result back into Eq. 4.7 gives us:
Now we have two different expressions for the j-th derivative of S with respect to n when setting n equal to zero. So now when we see that Eq. 4.6 and Eq. 4.12 are equal, we can write:
By cancelling out the common term j!/(p+1) we finally arrive at a recursive expression for the coefficients:
Note that the variable j in the above equation is redundant, and by taking into account the relation of Eq. 4.1 (j ≤ p), we can re-write the superscript p-j+1 as simply j, yielding:
We can write a more useful equation by noting that the smallest value of j is zero. In other words, the upper limit of the sum can be written as j+1(then the superscript j-i+1 becomes 0). This is so we don’t have to define coefficients where j < 0 where all these coefficients are equal to zero.
Our final equation for the coefficients:
One last interesting thing we can do here is derive a recursive equation to generate Bernoulli numbers. Remember that Bₚ=(p+1)a(p,p) (Eq. 4.2). Using this fact and the equation above yields:
5 — Deriving New Equations For Sₚ
Studying just the structure of Faulhaber’s formula (Eq. 3.1), playing around a bit, and by using our intuition, we can find new equations for Sₚ. It turns out that a very useful thing to do is to study the relationship between dSₚ/dn and Sₚ-₁. Using Eq. 3.1 we can write:
Upon first observation these two equations look very similar. We can re-write Eq. 5.1 to make them look even more similar:
Notice that we could work out the exact relationship between Eq. 5.2 and Eq 5.3 if we knew the relationship between a(j,p) and a(j,p-1).
One way to find that relationship is by making an educated guess based on intuition and then proving it. So then you might see that it would be very convenient if (p+1-i)a(j,p) = a(j, p-1). But after testing this for a few values you’d prove it false.
It would also be convenient if ( (p+1-i)/(p+1) ) a(j,p) = a(j, p-1). And then after testing it for a few values you’d find it seems to hold. But how do we prove it true? The answer is that we can prove it to be true by using Eq. 4.16 (the recursive formula for the coefficients). You can find this proof in the Appendix.
Using the proof found in the Appendix, we can write:
Now we can re-write Eq. 5.1 using this result:
By comparing Eq. 5.5 and Eq. 5.2 we can easily work out the relationship:
Integration then yields our first new formula:
With this formula we can generate any Sₚ using the p-th Bernoulli number and only the previous Sₚ. So this is already a more efficient recursive formula than the one we derived earlier (Eq. 2.9). It’s also quite easy to take an integral of a polynomial function (and from the structure of Sₚ we know the constant of integration will always be zero).
But there is, however, an even more efficient recursive formula that does not require reference to Bernoulli numbers at all.
Let us start by studying the initial case when n = 1:
As you can see we easily find that Sₚ(1) = 1.
Let us now substitute n = 1 into Eq. 5.7:
Re-writing above equation yields:
Then substituting this result into Eq. 5.7 gives us the second new recursive formula:
Now this is an interesting formula. With this one you can generate any Sₚ using only the previous Sₚ function and without using Bernoulli numbers.
6- Derivation Faulhaber’s Formula
Remember that in paragraph\ 3 I explained that Faulhaber’s formula directly generates the coefficients of Sₚ by using the relation that all the coefficients can be expressed in terms of the Bernoulli Numbers.
We can find this relation by using the recursive relation of the coefficients (Eq. 5.4) as proven in the Appendix and extending this relation to be more general. Let us first look at the following case:
Note that we simply applied the relation twice to relate a(j, p-2) to a(j, p). We can generalize this result to find the relation of a(j, p-t) to a(j,p):
Now what we need to do is to choose t such that we can express the j-th Bernoulli number in terms of a(j, p):
By using t = p — j and working out some algebra, we find:
Now we can simply use the structure we already set up for Faulhaber’s Formula (Eq. 3.1), substitute Eq. 6.4, and write out Faulhaber’s Formula:
Appendix —Proof Relation Coefficients
The relation to be proven (Eq. 5.4):
Recursive formula for the coefficients (Eq. 4.16):
Recursive formula for the coefficients for a(j, p-1):
If the relation holds true then we can re-write the above equation to get:
Note that the term p+1-j is independent of the summation index i and can thus be taken outside the summation.
Finally the following relation will be very useful (you can derive this for yourself):
Substituting this into the formula for a(j, p-1) we get:
□
