Deriving the Closed Form for Square Pyramidal Numbers

Published on

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.

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(2j−1)k^2 = \sum_{j=1}^k (2j-1)

since k2−(k−1)2=2k−1k^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=1n∑j=1k(2j−1).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=1n∑j=1k(2(k−j)+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=1n∑j=1k(2j−1)=∑j=1n∑k=jn(2j−1)=∑j′=1n∑k=n+1−j′n(2(n+1−j′)−1)=∑j′=1n∑k′=1j′(2(n−j′)+1)=∑k=1n∑j=1k(2(n−k)+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+1−jj' = n+1-j, change of variable k′=k+j′−nk' = k+j'-n, renaming j′→kj' \rightarrow k, k′→jk' \rightarrow j).

We now add together these three expressions for sns_n and get

3sn=∑k=1n∑j=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.