# Sum of Pairs of Integers less than N

What is the sum of all (ordered) pairs of integers less than N? That is, what is the value of this:

$\sum_{i \le n} \sum_{j \le n} ij$

Now this is very easy to determine. One way is to notice that it is the same as:

$(1+2+\ldots+n)^2 = \frac{1}{4}[n(n+1)]^2$

You can see this by imagining the expansion of square on the left hand side. Alternatively you can get the same result by just evaluating the sum in the obvious way. (Move the i outside the inner sum, evaluate the inner sum, and move the result out of the remaining sum.)

However, I have remarked before about how the square of the sum of the first N numbers is equal to the sum of the first N cubes. Therefore we have the equality:

$\sum_{i\le n}\sum_{j \le n} ij = \sum_{i \le n} i^3$

So this is easy to prove it is true by recognising what the sum on the left really is, but is there a more direct way of seeing it? It just isn’t obvious that the sum of the pairs of integers should be the sum of cubes less than that number!

In fact it is very easy to see. The sum can just be rewritten as:

$\sum_{i\le n}\sum_{j \le n} ij = \sum_{i\le n}\sum_{j \le i} ij + i(i-j)$

To convince yourself that no terms have been lost, note that on the left hand side there are $n^2$ terms, whilst on the right there are $2i-1$ for each i(There are not 2i as when i=j there is nothing for it to pair with) and so, using the formula for the sum of the first N numbers, there are $n^2$ terms on the right. Obviously no term has been repeated and so they are equal.

Then we just have:

$\sum_{i\le n}\sum_{j \le i} ij + i(i-j) = \sum_{i\le n}\sum_{j \le i} i^2 = \sum_{i\le n} i^3$

And so it is shown. A very simple result, but I like seeing these relationships directly.