On Sums of Powers of Consecutive Integers

As readers may be able to tell (from the subject of the previous post), I have recently become interested in properties of series. Today I will share how a certain geometric intuition has led me to a discovery of an interesting recursive relation for the sum of powers of consecutive integers. I have not been able to find a similar derivation or formula elsewhere on the web, but considering the history of the problem (dating back to Archimedes) I would be shocked if it has not been studied before.

k=1

To begin, we define $S_k(n)=\sum_{j=0}^n j^k = 1^k + 2^k + \cdots + n^k$, for all integers $k\geq 0$ and $n\geq 0$. Of course by definition $S_0(n)=n$, and simple geometric intuition suggests (and induction proves) that $S_1(n)=\frac{n(n+1)}{2}$.

The geometric argument is as follows: we can imagine a stack of boxes $n$ rows high (the figure below shows $n=4$).



The desired sum is obviously the total number of boxes (in this case 10), but how do we compute it in the general case? Notice that adjoining another stack of boxes (one with $n-1$ rows) forms a square with $n$ boxes on the side.



Algebraically, we can say $S_1(n)+S_1(n-1)=n^2,$ and since $S_1(n-1)=S_1(n)-n$, we have $2S_1(n)=n^2+n=n(n+1) \rightarrow S_1(n)=\frac{n(n+1)}{2}.$

k=2

What can we say about the sum of the squares of the first $n$ integers? For this it helps to imagine a pyramid of base $n \times n$ and height $n$. The $j$th level (starting from the top) of the pyramid is made up of $j^2$ boxes, and so the desired sum is just the total number of boxes in the pyramid. For $n=4$ the side view and overhead view are as follows:


The numbers in the figure to the right correspond to the number of blocks above each square on the base of the pyramid. This immediately suggests a method for summing the number of blocks - we will tally up those of like color. For a pyramid of base $n \times n$, the number is given by $S_2(n) = n+3(n-1)+5(n-2)+\cdots+(2n-1)=\sum_{i=0}^{n} (n-i)(2i+1).$

Thus we have $S_2(n)=\sum_{i=0}^{n} (n-i)(2i+1)$
$=\sum_{i=0}^{n}2in + \sum_{i=0}^{n}n - 2\sum_{i=0}^{n} i^2 - \sum_{i=0}^{n}i = 2nS_1(n)+nS_0(n)-2S_2(n)-S_1(n)$.

Collecting like terms and substituting our known expressions for $S_0(n)$ and $S_1(n)$ gives

$3S_2(n)=(2n-1)S_1(n)+nS_0(n)=\frac{n(n+1)(2n-1)}{2} +n^2= \frac{n(n+1)(2n+1)}{2}$

Dividing both sides by $3$ gives the well-known formula:

$S_2(n) = \frac{n(n+1)(2n+1)}{6}$.

k=3

We can proceed with the sums of cubes case analogously. This time we consider stacks of cubes of boxes, as illustrated by the following figures for $n=4$:



Once again, the pattern is clear. We have $S_3(n)=\sum_{i=0}^n \frac{n(n+1)-i(i+1)}{2}(2i+1)=\sum_{i=0}^n (S_1(n)-S_1(i))(2i+1).$ Expanding in a similar fashion yields the familiar formula:

$S_3(n)=(\frac{(n(n+1)}{2})^2=S_1(n)^2$

The clever reader may see a pattern and conjecture that for general $k\geq 2$:

$S_k(n)=\sum_{i=0}^{n}(S_{k-2}(n)-S_{k-2}(i))(2i+1).$

Needless to say proof by induction seems very tempting!