Re: fastest way to derive sum(k^3, for k=1, ...n)?

Johann Wiesenbauer

From:	Johann Wiesenbauer
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 23:53:13 +0000 (UTC)

On 22 Jan 2005, lucy wrote:
>Hi all,
>
>anybody recommends a fastest way to compute the
>
>sum(k^3, k=1...n)?
>
>I tried hard to remember this formula, but keep forgetting it...
>
>Everytime it took me quite a while to derive it...
>
>Any fastest way?
>
>thanks a lot!
>

In the first place, as already mentioned by others, the equation

sum(k^3, k=1..n) = sum(k, k=1..n)^2

holds.

As for the proof, imagine the LHS of this equation as the sum of cubes
(in a geometrical sense) with sides 1,2,..,n, where each cube with
side k is in turn composed by k^3 unit cubes. Now the RHS of the
equation abovesays that we can rearrange all those samll cubes that
they form a rectangular parallelepiped of height 1 such that the base
is a square with side sum(k, k=1,..n).

Assume that we have shown this for some n, say n=3 to make things
easier. The question is how to decompose the cube with side 4 in
order to get the appropriate bigger parallelepiped. Now this cube
can be considered as composed of 4 quadratic layers. If you number
the unit cubes of each layer in the following way

1 7 7 7
2 2 6 6
3 3 3 5
4 4 4 4

then it easy to see how to achieve this goal:

1 2 2 3 3 3 4 4 4 4
1 2 2 3 3 3 4 4 4 4
1 2 2 3 3 3 4 4 4 4
1 2 2 3 3 3 4 4 4 4
x x x x x x 7 7 7 7
x x x x x x 7 7 7 7
x x x x x x 7 7 7 7
x x x x x x 6 6 6 6
x x x x x x 6 6 6 6
x x x x x x 5 5 5 5

Again, this needs to be generalized to arbitrary n, but I leave this
out here as it is rather obvious.

Johann