Proof of Recursive Relation for the Sum of Powers of Consecutive Integers

I ended yesterday's post by suggesting that the recursive relation for the sum of powers of consecutive integers could be proven by means of mathematical induction. It turns out that this by no means seems trivial or natural; indeed a much more straightforward and natural approach is to use the geometric intuition that suggested the relation in the first place.

First we define some terms that will be used in the proof.

The cell $C_{i,j}$ for positive integers $i,j$ is the square region in $\mathbb{R}^2$ given by $\{(x,y) \in \mathbb{R}^2 | (i-1) \leq x < i $, $ (j-1) \leq y < j\}$. The box $C_{i,j,k}$ for positive integers $i,j,k$ is the cubic region in $\mathbb{R}^3$ given by $\{(x,y,z) \in \mathbb{R}^3 | (x,y)\in C_{i,j}$, $ (k-1) \leq z < k \}$. As the reader can see, cells partition the first quadrant of the plane, and boxes partition the first octant of $3$-space. For a positive integer $n$, we define the $n$-pyramid $P_n$ to be the set of boxes $C_{i,j,k}$ satisfying $i\leq n$, $j \leq n$ and $k \leq min(i,j)$. The $m$th level ($1\leq m \leq n$) of the pyramid $P_n$ is simply $\{C_{i,j,k} \in P_n | k=n-m+1\}$. This agrees more or less with the notion of an $n$-pyramid from the previous post, and I will spare the reader from trivial geometric verifications of the fact that the $m$th level contains $m^2$ boxes, among other things. Recall that the impetus for thinking about this pyramid is that the total number of boxes (given simply by counting level by level) is $\sum_{i=1}^n i^2.$

We also let $S_k(n)=\sum_{i=0}^n i^k$, in line with the notation used in the previous post. Now we can state and prove the main theorem.

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

Proof. We divide each box into $m^{k-2}$ compartments (where $m$ is the level of the box). Then $S_k(n)$ gives the total number of compartments in the pyramid. Consider the cell $C_{l,l}$. This cell has $l$ boxes above it (since $min(l,l)=l$), given by $\{C_{l,l,k}| 1\leq k \leq l \}$. Also note that all cells $C_{l,m}$ and $C_{m,l}$ with $m > l$ have l boxes above them (since in either case $min(m,l)=min(l,m)=l$). In each case the boxes occupy levels $(n-l+1), (n-l+2), \ldots , n$, and so each of these cells has the same number of compartments above it as $C_{l,l}$.

We can define an equivalence relation between the cells, such that two cells $C_{i,j} \sim C_{k,m}$ if and only if they have the same number of compartments above them. In light of the preceding discussion, it is easy to see that $C_{i,j} \sim C_{k,m}$ if and only if $min(i,j)=min(k,m)$. This relation partitions the $n^2$ cells at the base of the pyramid into $n$ disjoint equivalence classes, and we can take the diagonal cell $C_{i,i}$ as a representative of the $2(n-i)+1$ cells in each class.

The total number of compartments above cell $C_{i,i}$ is $n^{k-2}+(n-1)^{k-2}+\cdots+(n-i+1)^{k-2}=S_{k-2}(n)-S_{k-2}(n-i),$ and so the total number of compartments above each equivalence class is $(S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1)$. The total number of compartments in the pyramid is then given by:

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

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!