You are here
Homesum of powers
Primary tabs
sum of powers
Introduction
A sum of powers is a number expressible in the form
$1^{m}+2^{m}+\cdots+n^{m}$ 
where $m$ and $n$ are positive integers. Let us denote this sum by $S_{m}(n)$. It is a wellknown fact that when $m=1$, then we have the following equality
$S_{1}(n):=1+2+\cdots+n=\frac{n(n+1)}{2}.$ 
In fact, a famous story goes that, when the teacher asked the students to sum up all the integers from 1 to 100, Gauss, at the age of 10, solved the problem immediately. Gauss realized that the sum can be written in two ways
$\underbrace{\xymatrix@R=0pt@C=0pt{&1&+&2&+&\cdots&+&n&&\\ &n&+&(n1)&+&\cdots&+&1&&\\ \ar@{}[rrrrrrrr]&&&&&&&&\\ &(n+1)&+&(n+1)&+&\cdots&+&(n+1)&&}}_{{\displaystyle{n}\mbox{ terms}}}$ 
Therefore, $2S_{1}(n)=n(n+1)$ and hence the result: $1+2+\cdots+100=\frac{100(101)}{2}=50\cdot 100=5050$.
What Gauss did is actually a special case of a method that can be generalized to the case when $m>1$. Thinking of a number $i$ as $1$ added to itself $i$ times, then using the following diagram:
$\xymatrix@R=0pt@C=0pt{&1&&&&&&&&1&&\\ &1&+&1&&&&&&2&&\\ &\vdots&&\vdots&&\ddots&&&&\vdots&&\\ &1&+&1&+&\cdots&+&1&&n&&\\ \ar@{}[rrrrrrrr]&&&&&&&&\ar@{}[rr]&&\\ &n&+&(n1)&+&\cdots&+&1&&S_{1}(n)&&}$ 
Using the summation notation, it then follows that
$\sum_{{i=1}}^{n}(ni+1)=n+(n1)+\cdots+1=S_{1}(n)=1+2+\cdots+n=\sum_{{i=1}}^{n% }i.$ 
Then,
$S_{1}(n)=\sum_{{i=1}}^{n}(ni+1)=\sum_{{i=1}}^{n}(n+1)\sum_{{i=1}}^{n}i=(n+1)% \sum_{{i=1}}^{n}1S_{1}(n)=(n+1)nS_{1}(n),$ 
and we have the same result.
Let us now apply this method to the case when $m=2$. This time, we use the following diagram
$\xymatrix@R=0pt@C=0pt{&1&&&&&&&&S_{1}(1)&&\\ &1&+&2&&&&&&S_{1}(2)&&\\ &\vdots&&\vdots&&\ddots&&&&\vdots&&\\ &1&+&2&+&\cdots&+&n&&S_{1}(n)&&\\ \ar@{}[rrrrrrrr]&&&&&&&&\ar@{}[rr]&&\\ &n\cdot 1&+&(n1)\cdot 2&+&\cdots&+&1\cdot n&&T&&}$ 
Again, using the summation notation, we have
$\sum_{{i=1}}^{n}(ni+1)i=T=\sum_{{i=1}}^{n}S_{1}(i)=\sum_{{i=1}}^{n}\frac{i(i+% 1)}{2}.$ 
Further algebraic manipulations give us the result:
$S_{2}(n):=1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6}.$ 
The general case
Using the method above, one can iteratively solve for $S_{3}(n),S_{4}(n),\ldots$. This means that if we know the formulas for $S_{k}(n)$ for all $k<p$, then we can derive the formula for $S_{m}(n)$. The formulas for $m=3,4,5$ and $6$ are
$m$  $S_{m}(n)$ 

$3$  $\displaystyle{\frac{n^{2}(n+1)^{2}}{4}}$ 
$4$  $\displaystyle{\frac{n(n+1)(2n+1)(3n^{2}+3n1)}{30}}$ 
$5$  $\displaystyle{\frac{n^{2}(n+1)^{2}(2n^{2}+2n1)}{12}}$ 
$6$  $\displaystyle{\frac{n(n+1)(2n+1)(3n^{4}+6n^{3}3n+1)}{42}}$ 
Remarks.
1. Notice that the formula for each of the powers $m=1,2,\ldots,6$ is always a polynomial of degree $m+1$. This is in fact true in the general case, and can be proved by the method of telescoping sum, together with induction: for each positive integer $n$, define
$x_{n}:=n^{{m+1}}(n1)^{{m+1}}.$ Then $x_{n}$ is expressible as a polynomial $y(n)$ of degree $m$ in $n$. So
$n^{{m+1}}=x_{n}+x_{{n1}}+\cdots+x_{1}=\sum_{{i=1}}^{n}y(i)=a_{m}\sum_{{i=1}}^% {n}i^{m}+a_{{m1}}\sum_{{i=1}}^{n}i^{{m1}}+\cdots+a_{0}\sum_{{i=1}}^{n}1.$ The right hand side is $a_{m}S_{m}(n)+a_{{m1}}S_{{m1}}(n)+\cdots+a_{0}n$. By induction, each $S_{k}(n)$ is a polynomial of degree $k+1$ for all $k<m$. But then right hand side is equal to the left hand side, which is a polynomial of degree $m+1$. Therefore, $S_{m}(n)$ is a polynomial of degree $m+1$. So we can safely write
$S_{m}(n)=c_{0}+c_{1}n+\cdots+c_{{m+1}}n^{{m+1}}.$ 2. Another property of $S_{m}(n)$ is that $c_{0}+c_{1}+\cdots+c_{{m+1}}=1$ for any $m$. This is clear, since, one the one hand, $S_{m}(1)=1$ as a sum of just one term $1^{m}$. On the other hand, its polynomial representation evaluated at $n=1$ is just the sum of the coefficients.
3. In addition, there are also two curious properties:

for each $m>0$, both $n$ and $n+1$ divide $S_{m}(n)$, and
These can be proved using the method above. For example, to show that $nS_{m}(n)$, use the expression
$n^{{m+1}}=\sum_{{i=1}}^{n}y(i)=a_{m}\sum_{{i=1}}^{n}i^{m}+a_{{m1}}\sum_{{i=1}% }^{n}i^{{m1}}+\cdots+a_{0}\sum_{{i=1}}^{n}1,$ and notice that the left hand side is divisible by $n$, and therefore so is the right hand side. Since all sums with powers $k<m$ are divisible by $n$ (induction), so is the sum with power $m$, and hence $nS_{m}(n)$. From this, one also sees that
$S_{m}(n)=\sum_{{i=1}}^{n}i^{m}=(n+1)^{m}+\sum_{{i=1}}^{{n+1}}i^{m}$ is divisible by $n+1$ as well.

4. Since $(n+1)S_{m}(n)$, we may write $S_{m}(n)$ as a polynomial in terms of $n+1$:
$S_{m}(n)=d_{1}(n+1)+d_{2}(n+1)^{2}+\cdots+d_{{m+1}}(n+1)^{{m+1}}.$ Notice that there is no coefficient for the constant term. It turns out that, when $S_{m}(n)$ is written this way, the coefficients are much easier to express. Jacques Bernoulli gave the formula for the coefficients:
$d_{i}=\frac{B_{{m+1i}}}{m+1}\binom{m+1}{i},$ (1) where $B_{k}$ is the $k$th Bernoulli number. The formula for $S_{m}(n)$ using the polynomial representation with the coefficients $d_{i}$ is called the Faulhaber’s formula, since Faulhaber first wrote down the polynomial in this form in 1631 (before Bernoulli).
5. The Faulhaber’s formula can actually be extended to all real numbers. In other words, $S_{m}(x)$ can be viewed as a polynomial of degree $m+1$ in the real variable $x$ with coefficients $d_{i}$ described by $(1)$. When $x$ is some positive integer $n$, we are back to the formula for the sum of $m$th powers of integers $1$ through $n$. In general, $S_{m}(x)$ is the indefinite sum of $x^{m}$:
$S_{m}(x)=\Delta^{{1}}x^{m}.$ 6. When $m<0$, we have what is known as the $m$series of order $n$ with the special case $m=1$ the harmonic series (of order $n$). There are no polynomial representations for $S_{m}(n)$ when $m<0$.
References
 1 A. F. Beardon, Sums of Powers of Integers, Amer. Math. Monthly 103 (1996), pp. 201213.
 2 R. Cook, On Sums of Powers of Integers, J. Number Theory 11 (1979), pp. 516528.
 3 R. W. Owens, Sums of Powers of Integers, Math. Mag 65 (1992), pp. 3840.
Mathematics Subject Classification
40A05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Corrections
Why p? by rm50 ✓
c_i simpler than? by rm50 ✓
External link broken by rm50 ✓
Notation by rm50 ✓
Comments
sum of powers  equivalent formulation
Here, Mr. Chi Woo, is what I think is an equivalent formulation to the "triangle" method you so elegantly present in your article, "sum of powers".
The key is to begin by reformulating s(n,k)  directly  as a recursion on sum(s(j,k1)), j=1,...,n1.
Express column A as column B. (And B translates to C.)
Your method begins with (something close to the) complementary upper triangle  which is blank in the formulation sketched below.

Express column A as column B. (And B translates to C.)
Your method begins with (something close to the) complementary upper triangle (left blank in the sketched below).
A B C
1**k 1 * 1**(k1) 1**(k1)
2**k 2 * 2**(k1) 2**(k1) + 2**(k1)
. .
. .
. .
n**k n * n**(k1) n**(k1) + n**(k1) + ... + n**(k1)
   +  + ... + 
s(n,k) s(n,k) s(n,k1) + s(n,k1) + ... + s(n,k1)
 s(1,k1)  ...  s(n1,k1)
or, in summary,
n1
s(n,k) = (n * s(n,k1))  sum (s(r,k1))
r=1

If you see fit to reply, I'm hope I will be able to find it, being quite new to PlanetMath.
Tom Lewinson
Re: sum of powers  equivalent formulation
Sorry for the mess I made of my original reply. Would love to delete it if I knew how. Am new to PlanetMath and don't know how to preserve white space.

I offer what is perhaps a trivial though I think not uninteresting equivalent alternative point of departure to the recursive "triangle" method you describe.
We have the definition of sum of kth powers,
A
1**k
2**k
.
j**k
.
.
n**k

s(n,k)
We then reformulate A as B, below,
B
(1) * (1**(k1))
(2) * (2**(k1))
.
(j) * (j**(k1))
.
.
(n) * (n**(k1))

s(n,k)
The key idea is rewriting the jth line in B as a sum instead of a product, that is, as a sum of j terms, j**(k1).
We then get a triangular array which is close to a sort of complementary array to the one you work with.
This approach has the possibly slight advantage in that it expresses the sum of kth powers  directly  as a recursion.
s(n,k) = (n * s(n,k1)) 
n1
sum (s(r,k1))
r=1
