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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: