# Chaitanya's Random Pages

## October 24, 2010

### My Six Favourite Formulas – #6

Filed under: mathematics — ckrao @ 11:02 am

This is the most elementary of my favourite formulas. I think I first saw this as a Year 8 student and have been enthralled by it ever since.

$\displaystyle \left(\sum_{n=1}^N n \right)^2 = \sum_{n=1}^N n^3$

In words, the sum of the first N cubes is the square of the sum of the first N squares. Furthermore, both sides are equal to the square of the binomial coefficient $\displaystyle \binom{N+1}{2} = \frac{N(N+1)}{2}$.

The formula was discovered by Aryabhata of Patna around 1500 years ago, but it may have been known before then. The most elementary proof is probably one by mathematical induction:

Let S be the set of positive integers N for which $\left(\sum_{n=1}^N n \right)^2 = \sum_{n=1}^N n^3$. We wish to show that S is the set of all positive integers $\mathbb{N}$.  Firstly $1 \in S$ since for N=1, $\text{LHS} = 1^2 = 1^3 = \text{RHS}$ . Assume $k \in S$. That is,

$\displaystyle \left(\sum_{n=1}^k n \right)^2 = \sum_{n=1}^k n^3.$

For convenience denote by $T$ the sum $\sum_{n=1}^k n = k(k+1)/2$. Then

$\begin{array}{lcl} \sum_{n=1}^{k+1} n^3 &=& (k+1)^3 + \sum_{n=1}^k n^3\\&=& (k+1)(k+1)^2 + T^2\quad \text{(by the inductive assumption)}\\ &=& T^2 + (k+1)[k(k+1) + (k+1)]\\&=&T^2 + (k+1)[2T + (k+1)]\\ &=& T^2 + 2T(k+1) + (k+1)^2\\&=& (T + (k + 1))^2\\ &=& \left(\sum_{n=1}^{k+1} n \right)^2.\end{array}$

This shows that if $k \in S$, then $k+1 \in S$. Hence by the principle of mathematical induction, $S = \mathbb{N}$ and we are done.

Next I will show the nicest proof that I am aware of (see p126 of [1] which also contains a proof by picture). We form the grid of numbers of the form $ij$ for i and j from 1 to N (as you would see in the multiplication tables) and sum the numbers of the grid in two ways. Below is an example for the case N=5.

 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 5 10 15 20 25

The easier sum is simply $\displaystyle \sum_{i=1}^N \sum_{j=1}^N ij = \left(\sum_{i=1}^N i \right) \left(\sum_{j=1}^N j \right) = \left(\sum_{i=1}^N i \right)^2,$ the left side of the formula.

Secondly, we sum along L-shapes, an example of which is shown in bold below.

 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 5 10 15 20 25

Note that each number in such an L-shape is a multiple of max(i,j), which ranges from 1 to N. The sum of the numbers in an L-shape is then this multiple times the sum of 1, 2, …, max(i,j)-1, max(i,j), max(i,j) – 1, …, 2, 1, which can easily be shown to be $\max(i,j)^2$ (think of counting the points of a square grid along diagonals). Hence the total is

$\displaystyle 1.1^2 + 2.2^2 + \ldots N.N^2 = \sum_{n=1}^N n^3$.

In other words,

$\begin{array}{lcl} \sum_{i=1}^N \sum_{j=1}^N ij &=& \sum_{i=1}^N \sum_{j=1}^N \max(i,j) \min(i,j)\\&=& \sum_{n=1}^N n \sum_{\max(i,j) = n} \min(i,j)\\&=& \sum_{n=1}^N n \left(\min(n,n) + \sum_{i=1}^{n-1} i + \sum_{j=1}^{n-1} j\right)\\&=& \sum_{n=1}^N n \left(n + \sum_{i=1}^{n-1} i + \sum_{i=1}^{n-1} (n-i)\right)\\&=&\sum_{n=1}^N n \left(n + \sum_{i=1}^{n-1} n\right)\\&=& \sum_{n=1}^N n(n + n(n-1)) \\&=& \sum_{n=1}^N n^3.\end{array}$

Reference:
[1] C. Alsina and R. Nelsen, “An Invitation to Proofs Without Words”, Eur. J. Pure Appl. Math, 3 (2010), 118-127, available here.