janmr blog

Deriving the Closed Form for Square Pyramidal Numbers

The sum of the first nn squares is

sn=k=1nk2=16n(n+1)(2n+1).s_n = \sum_{k=1}^n k^2 = \textstyle\frac{1}{6} n (n+1) (2n+1) \quad .

The numbers s0,s1,s2,s_0, s_1, s_2, \ldots are called the square pyramidal numbers.

Many different proofs exist. Seven different proofs can be found in Concrete Mathematics and even a visual proof has been published (via @MathUpdate).

One of the simplest proofs uses induction on n. This approach assumes that you know (or guess) the correct formula beforehand, though.

This post will show a derivation which is a formalization of the derivation shown on wikipedia. It revolves around manipulating sums and the fact that

k2=j=1k(2j1)k^2 = \sum_{j=1}^k (2j-1)

since k2(k1)2=2k1k^2 - (k-1)^2 = 2k-1.

We will now write sns_n in three different ways. The first simply inserts the above expression for k2k^2:

sn=k=1nj=1k(2j1).s_n = \sum_{k=1}^n \sum_{j=1}^k (2j-1) \quad .

The second reverses the order of summation for the inner sum:

sn=k=1nj=1k(2(kj)+1).s_n = \sum_{k=1}^n \sum_{j=1}^k (2(k-j)+1) \quad .

The third starts as the first and does a series of manipulations:

sn=k=1nj=1k(2j1)=j=1nk=jn(2j1)=j=1nk=n+1jn(2(n+1j)1)=j=1nk=1j(2(nj)+1)=k=1nj=1k(2(nk)+1)\begin{aligned} s_n &= \sum_{k=1}^n \sum_{j=1}^k (2j-1) = \sum_{j=1}^n \sum_{k=j}^n (2j-1) = \sum_{j'=1}^n \sum_{k=n+1-j'}^n (2(n+1-j')-1) \\ &= \sum_{j'=1}^n \sum_{k'=1}^{j'} (2(n-j')+1) = \sum_{k=1}^n \sum_{j=1}^k (2(n-k)+1) \end{aligned}

(the manipulations being: Switching the order of summation, change of variable j=n+1jj' = n+1-j, change of variable k=k+jnk' = k+j'-n, renaming jkj' \rightarrow k, kjk' \rightarrow j).

We now add together these three expressions for sns_n and get

3sn=k=1nj=1k(2n+1)=(2n+1)k=1nk=(2n+1)n(n+1)23 s_n = \sum_{k=1}^n \sum_{j=1}^k (2n+1) = (2n+1) \sum_{k=1}^n k = (2n+1) \frac{n (n+1)}{2}

which, after dividing each side by 3, produces the wanted formula.