The Gaussian Sums of Powers
Back to Contents
Add up all of the squares of the natural numbers from one to N in the manner of a Gaussian sum. What number do you calculate? What number do you calculate if you sum all of the cubes of the natural numbers from one to N? If you sum the quartics? The quintics? The sextics?
In 1631 Johann Faulhaber (1580 May 05 B 1635 Sep 10) addressed that problem in his book Academia Algebra. He was able to work out the formulae describing the sums of powers up to the 23rd, but he did not come up with a general formula that would apply to the sums of all possible powers of the positive integers.
Fortunately Leonhard Euler (1707 Apr 15B 1783 Sep 18) discovered a straightforward way of devising just the formula that we want for that calculation. He started out with what looks like a Maclaurin series: given some function f(x), we have
Summing that equation with respect to all relevant values of x, beginning at zero, gives us
But we also know that
in which A represents some constant, stands true to mathematics, so we can combine that equation with Equation 2 to get
which we can rearrange into
That is Euler's summation formula. Let me note here that sometimes people make the substitution z=df/dx to make the formula look cleaner. I have chosen to retain the raw form of Equation 5 because I believe it is more transparent.
Thus we take the first step in our derivation. Next we must, as Euler did, apply that formula to calculating the sums of the powers of x.
Let us take f(x)=xn+1. We have in this case A=0, so we get
Because that formula contains the sums of the lower powers of x, in order to devise the formula for the given power of x we must build up the sums of the lower powers in sequence. Thus we start with the obvious
We then work out
which gives us the basic Gaussian sum of the natural numbers up to x. Next we work out the sum of the squares of x,
Continuing that process and organizing the results gives us a triangular array:
We see more or less immediately that we can generate the n-th row of that array from the (n-1)-th row by applying two simple rules:
1. Generate the i-th element of the n-th row of that array by multiplying the i-th element in the (n-1)-th row by nx/(n+2-i). We infer that multiplier by simply dividing the i-th of the n-th row by the i-th element of the (n-1)-th row for several rows and then identifying the pattern that emerges. It helps that process if we choose the rows such that one of the row indices is a prime number (e.g. n=7 or n=5). We extend this result to all values of n by induction: Euler's summation formula works the same for all values of n and nothing else changes as the value of n changes; therefore, the formula that we infer for the multiplier also works the same for all values of n. Q.E.D.
2. We complete the n-th row by adding to it the term Cnx in which
in which Ci represents the coefficients of the i-th term. We base that calculation upon the fact that
which we verify for any row by letting x=1. Note that for even values of n the Cn comprise the set of the Bernoulli numbers in accordance with Cn=Bn/2.
In general we have
in which we have the binomial coefficients
In Equation 12 we also see the Bernoulli numbers, represented as Bi. We thus have our formula for calculating the sum of the integers, in sequence, raised to some power.
Appendix: Proof of Equation 3
Equation 3 looks more than a little suspicious to me, but it does so because, as Euler did, I left the indices off of the summation signs. If we sum f(x-1) from x=1 to x=N we get the same result that we would get from summing f(x) from x=0 to x=N-1. If we sum both f(x-1) and f(x) between x=1 and x=N, as Equation 3 implies, then the sum of f(x) gives a term f(N) too much and a term f(0)=A too little. Thus to the sum of f(x) we must add the constant term A=f(0) and subtract the term f(N). We then obtain, more explicitly,
which is just Equation 3.
Back to Contents