I recently proved that
$$\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k \right)^2$$
using mathematical induction. I'm interested if there's an intuitive explanation, or even a combinatorial interpretation of this property. I would also like to see any other proofs.
On
There's this nice picture from the Wikipedia entry on the squared triangular number:
The left side shows that $1 + 2 + 3$ forms a triangle and so that squaring it produces a larger triangle made up of $1+2+3$ copies of the original triangle. The right side has $1(1^2) + 2(2^2) + 3(3^2) = 1^3 + 2^3 + 3^3$. The coloring shows why the two sides are equal.
There are several other references for combinatorial proofs and geometric arguments on the Wikipedia page.
On
Chance would have it that I stumbled* upon this article today:
http://blogs.mathworks.com/loren/2010/03/04/nichomachuss-theorem/
It seems to answer your question.
(* That is, @AlgebraFact on Twitter posted a link)
On
I don't know if this is intuitive, but it is graphic.
On the outer edge of each $(k{+}1){\times}k$ block there are $k$ pairs of products each of which total to $k^2$. Thus, the outer edge sums to $k^3$, and the sum of the whole array is therefore $\sum\limits_{k=1}^n k^3$.
The array is the matrix product $$ \left[\begin{array}{r}0\\1\\2\\\vdots\\n\end{array}\right]\bullet\left[\begin{array}{rrrrr}1&2&3&\cdots&n\end{array}\right] $$ Therefore, the sum of the elements of the array is $\sum\limits_{k=0}^nk\;\sum\limits_{k=1}^nk=\left(\sum\limits_{k=1}^nk\right)^2$.
Therefore, $\sum\limits_{k=1}^n k^3=\left(\sum\limits_{k=1}^nk\right)^2$
On
Here's another version of this "proof without words". This is the case $n=4$.
There are 1 $1 \times 1$, 2 $2 \times 2$, 3 $3 \times 3$, ... squares, for a total area of $1^3 + 2^3 + \ldots + n^3$. For even $k$, two of the $k \times k$ squares overlap in a $k/2 \times k/2$ square, but this just balances out a $k/2 \times k/2$ square that is left out, so the total is the area of a square of side $1 + 2 + \ldots + n$.
On
Can you get the intuition explanation from the following two pictures?[EDIT: the following is essentially the same as Mariano's answer. He didn't mentioned the first picture though.]
The images are from Brian R Sears.
On
The sum of a degree $n$ polynomial $f(n)$ will be a degree $n+1$ polynomial $S(n)$ for $n \geq 0$ and both polynomials can be extended (maintaining the relation $S(n)-S(n-1) = f(n)$) to negative $n$. To verify that the formula for $\Sigma k^3$ is correct one need only test it for any 5 distinct values of $n$, but the structure of the answer can be predicted algebraically using the continuation to negative $n$.
If $S(n) = (1^3 + 2^3 + \dots n^3)$ is the polynomial that satisfies $S(n)-S(n-1) = n^3$ and $S(1)=1$, then one can calculate from that equation that $S(0)=S(-1)=0$ and $S(-n-1)=S(n)$ for all negative $n$, so that $S$ is symmetric around $-1/2$. The vanishing at 0 and -1 implies that $S(t)$ is divisible as a polynomial by $t(t+1)$. The symmetry implies that $S(t)$ is a function (necessarily a polynomial) of $t(t+1)$.
$S(t)$ being of degree 4, this means $S(n) = a (n)(n+1) + b((n^2 +n)^2$ for constants $a$ and $b$. Summation being analogous to integration (and equal to it in a suitable limit), they have to agree on highest degree terms. Here it forces $b$ to be $1/4$ to match $\int x^3 = x^4/4$. Computing the sum at a single point such as $n=1$ determines $a$, which is zero.
Similar reasoning shows that $S_k(n)$ is divisible as a polynomial by $n(n+1)$ for all $k$. For odd $k$, $S_k(n)$ is a polynomial in $n(n+1)$.
On
http://en.wikipedia.org/wiki/Faulhaber%27s_formula#Faulhaber_polynomials
If $p$ is odd, then $1^p+2^p+3^p+\cdots+n^p$ is a polynomial function of $a=1+2+3+\cdots+n$. If $p=3$, then then the sum is $a^2$; if $p=5$ then it's $(4a^3-a^2)/3$, and so on.
On
Each colored area is $k^3$ as a difference of two areas: $S_k^2 - S_{k-1}^2$.
The detailed proof which comes with the drawing is the following.
For any positive integer $k$, we define: $$S_i = \sum_{j=1}^{i} j$$
We first notice: $$S_i^2 = S_i^2 - S_0^2= \sum_{k=1}^{i} \left(S_k^2 - S_{k-1}^2\right)$$
The expected result finally comes from: $$S_k^2 - S_{k-1}^2 = k \left(k+2 S_{k-1}\right) = k\left(k+k\left(k-1\right)\right)=k^3$$
On
You know, $\sum_0^n x^k=\frac{1-x^{n+1}}{1-x}$. Differentiate both sides once, $\sum_1^n kx^{k-1}=\frac{x^n(nx-n-1)+1}{x^2-2x+1}$. Now taking $\lim_{x\to1}$ both sides and then squaring the result will give you the expression on the RHS. You can further differentiate $\sum_0^n x^k=\frac{1-x^{n+1}}{1-x}$ until you get $k^3$ inside the expression, take limit again you will get the same result as of $\left(\lim_{x\to1}\frac{x^n(nx-n-1)+1}{x^2-2x+1}\right)^2$. You can also prove it using telescopic series.
On
We know that $$A=\sum_1^n k^3=\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2$$ and $$B=\sum_1^n k=\frac{1}{2}n^2+\frac{1}{2}n$$ $A-B^2=0$. :)
On
Several visual proofs of this indentity are collected in the book Roger B. Nelsen: Proofs without Words starting from p.84.
Although several of these proofs can still be considered inductive, I thought it might be interesting to mention them.
Original sources are given on p. 147:
On
$f(n)=1^3+2^3+3^3+\cdots+n^3$
$f(n-1)=1^3+2^3+3^3+\cdots+(n-1)^3$
$f(n)-f(n-1)=n^3$
if $g(n)= (1+2+3+4+\cdots+n)^2$ then
$$g(n)-g(n-1)=(1+2+3+4+\cdots+n)^2-(1+2+3+4+\cdots+(n-1))^2$$
using $a^2-b^2=(a+b)(a-b)$
$$\begin{align}g(n)-g(n-1)&=\\ &=[(1+\dots+n)+(1+\dots +(n-1))][(1+\dots+ n)-(1+\dots+(n-1)]\\ &=[2(1+2+3+4+\cdots+(n-1))+n]n\\ &=\left(2\frac{n(n-1)}{2}+n\right)n\\ &==(n(n-1)+n)n\\ &=n^3 \end{align}$$
$f(n)-f(n-1)=g(n)-g(n-1)=n^3$ for all $n$ and if $f(0)=g(0)$ then
$f(n)$ and $g(n)$ are equal and we can write $$1^3+2^3+3^3+\cdots+n^3=(1+2+3+4+\cdots+n)^2$$
On
You've gotta see it to believe it.
In formulas:
$$(\sum k)^2=\sum j^2 + 2 \sum_{i<j} ij =\sum_j (j^2+2 \sum_{i<j} ij)=\sum_j j(j+j(j-1))=\sum_j j(j^2)=\sum_j j^3$$
In words: we can assemble the square with side $(1+...+k)$ from $k$ smaller squares and pairs of rectangular blocks. If we look only at the rectangular blocks with the largest side fixed to some size $j$, they all pair up into $j-1$ "complementary" pairs (based on the size of the smaller side, pairing $1$ with $j-1$, $2$ with $j-2$, untill $j-1$ with $j$; this is Gauss' trick), each pair of rectangles forming a $j$ by $j$ square together. Thus, together with the $j^2$ piece they assemble into a cube of side $j$.
On
This answer uses the same sort of reasoning as given in the answer by zyx. I show that we can get a bit more out of the recursion relation satisfied by the function $S(n)$ and their generalizations for summation of arbitrary powers, in particular that $S(t)$ (and its generalization for summations over odd powers larger than 1) contains a factor $t^2 (1+t)^2$. This then immediately establishes the result.
We start with defining the functions $S_k(n)$:
$$ S_k(n) =\sum_{r=0}^{n}r^k \tag{1}$$
where $k$ and $n$ are integers and we take $k\geq 1$ and $n\geq 0$. The functions $S_k(n)$ satisfy the recursion:
$$ S_k(n) - S_k(n-1) = n^k \tag{2}$$
This recursion together with the condition that $S_k(0) = 0$ which follows from (1), fixes the function $S_k(n)$. In particular, it follows from this that $S_k(n)$ is a polynomial of degree $k+1$ in $n$. This means that we can lift the constraint that $n$ be an integer larger than or equal to zero and instead take $n$ to be any arbitrary real or complex number.
If we put $n = 0$ in (2) and use that $S_k(0) = 0$, we find:
$$S_k(-1) = 0$$
The function $S_k(x)$ is therefore a polynomial of degree $k+1$ which contains a factor of $x (x+1)$. Since $S_1(x)$ is a second degree polynomial, this fixes $S_1(x)$ up to a constant factor, and we can find that this factor is $\frac{1}{2}$ by using $S_k(1) = 1$, although that's not necessary to do for the purpose of this problem.
We can find a symmetry relation satisfied by $ S_k(n)$ using the recursion (2) as follows. We replace $n$ by $-n$ to obtain:
$$ S_k(-n) - S_k(-n-1) = (-1)^k n^k $$
Let’s define the function $\tilde{S}_{k}(n) = S_k(-n)$. We can then write the above recursion as:
$$ \tilde{S}_k(n+1) - \tilde{S}_k(n) = (-1)^{k+1} n^k $$
We then see that the function $(-1)^{k+1}\tilde{S}_k(n+1)$ satisfies the same recursion as the function $S_k(n)$. The value at $n = 0$ is equal to zero, because $\tilde{S}_k(1)= S_k(-1) = 0$. This means that these two functions are identical. We thus have:
$$ S_k(-x-1) = (-1)^{k+1}S_k(x)$$
The point at which $x = -x - 1$ is $x = -\frac{1}{2}$. We see that for even $k$, $S_k(x)$ is anti-symmetric w.r.t. reflection about this point, while in case of odd $k$, it is symmetric. This means that for even $k$, the function has a zero there, while for odd $k$ the derivative is zero:
$$ \begin{split}S_{2k}\left(-\frac{1}{2}\right) &= 0\\ S'_{2k+1}\left(-\frac{1}{2}\right) &= 0\end{split}$$
This fixes $S_2(x)$, because $S_2(x)$ is a third degree polynomial and it has zeros at $x = 0$, $x = 1$ and $x = -\frac{1}{2}$, so it’s proportional to $x (x+1)(2x+1)$, and demanding that $S_2(1) = 1 $ yields $S_2(x) = \frac{1}{6} x (x+1)(2x+1)$. Obtaining this expression is, however, not necessary for the purpose of this problem.
In general, we have that $S_{2k}(x)$ contains a factor of $x(x+1)(2x+1)$. We can obtain more information about $S_k(x)$ for odd $k$ by taking the derivative of the recursion (2). This yields:
$$ S'_{2k+1}(x) - S'_{2k+1}(x-1) = (2k+1) x^{2k}$$
We then see $\frac{S'_{2k+1}(x)}{2k+1}$ satisfies the same recursion as $S_{2k}(x)$. Because both these functions are zero at $x = -\frac{1}{2}$, they are identical. The fact that $S_{2k}(x)$ is zero at $x = 0$ and $x = 1$ then tells us that $ S'_{2k+1}(x)$ is zero there as well. So, we see $S_{2k+1}(x)$ has zeros at $x = 0$ and $ x = 1$ of multiplicity of at least $2$, so $S_{2k+1}(x)$ contains a factor of $x^2 (x+1)^2$.
In particular, since $S_3(x)$ is a fourth degree polynomial, we see that it is proportional to $x^2(x+1)^2$, so it's proportional to $ S_1(x)^2$. And since $ S_k(1) =1 $for all $k$, we have $S_3(x) = S_1(x)^2$.
Stare at the following image, taken from this MO answer, long enough: