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!

The Cauchy Condensation Test

For my first post, I decided to share an interesting little theorem I came across (and decided to prove) called the Cauchy Condensation Test. It provides a criterion for deciding whether a certain series (with positive decreasing terms) converges. It is useful in that the p-series test falls out somewhat naturally from it.

Theorem 1 (Cauchy Condensation Test). Let $\sum_{i=1}^\infty a_k$ be a series of positive terms with $a_{k+1} \leq a_k$. Then $\sum a_k$ converges if and only if $\sum_{k=0}^\infty 2^k a_{2^k}$ converges.

Proof. Let $A_n = \sum_{k=1}^n a_k$. Suppose first that $(A_n)$ converges. We will show that $\sum_{k=0}^\infty 2^k a_{2^k}$ converges.

For this we consider the sum $\sum_{k=1}^\infty s_k = \sum_{k=1}^\infty 2^{k-1} a_{2^k}$. The idea here is to group the $a_k$ terms so that each $s_k$ is bounded by a sum of $a_k$s (with each $a_k$ being used only once). Since the $a_k$ terms are decreasing, it follows that $2^{k-1}a_{2^k} \leq a_{2^{k-1}+1}+\cdots + a_{2^k}.$ Summing from $1$ to $n$ then gives:

$\sum_{k=1}^n 2^{k-1} a_{2^k} \leq \sum_{k=1}^n a_{2^{k-1}+1}+\cdots + a_{2^k} \leq A_{2^n} < \lim_{n\to \infty} A_n=C$, for some constant $C$. As $n\to \infty$, the sum stays bounded, and so must converge (since the sequence of partial sums is then monotone increasing and bounded) to some value $S$. It is then easy to see that $\sum_{k=0}^\infty 2^k a_{2^k}$ converges to $2S+a_1$. A similar sort of idea works for the reverse direction, except this time we can use the sum directly. Consider $A_{2^{k}-1}=a_1+(a_2+a_3)+\cdots+(a_{2^{k-1}}+\cdots+a_{2^k-1}).$ Again since the terms are decreasing, we can bound each term by the first term in its group (denoted by parenthesis): $RHS \leq a_1 +2a_2 + \cdots + (2^{k}-1)a_{2^{k}-1} \leq \sum_{k=0}^{k} 2^k a_{2^k} \leq \sum_{k=0}^{\infty} 2^k a_{2^k} = C$, for some constant $C$. Thus we have $A_{2^k-1} \leq C$, and letting $k\to \infty$ shows that the series converges.

Note: The "shifting" idea behind this proof can also be used to prove the famous Integral Test for series, which says that if $f$ is continuous, nonnegative, and monotone decreasing on $[1,\infty)$, then $\sum_{i=1}^\infty f(i)$ and $\int_1^\infty f(x)dx$ converge or diverge together.

Now for an application of the Cauchy Condensation Test, we show how it leads to an easy proof of the $p$-series test. The $p$-series test says that $\sum_{k=1}^\infty \frac{1}{k^p}$ converges if $p > 1$ and diverges to $\infty$ if $p\leq 1$.

We can thus turn to the series $\sum_{k=1}^\infty 2^k \frac{1}{2^{kp}}=\sum_{k=1}^\infty {2^{(1-p)}}^k$. Seemingly miraculously, we have gone from considering a $p$-series to a much simpler geometric series! We can easily see that this series converges if $p>1$ and diverges to $\infty$ if $p\leq 1$. By the condensation test, the series $\sum_{k=1}^\infty \frac{1}{k^p}$ must do the same.