# Proving the identity $\sum\limits_{k=1}^n {k^3} = {\Large(}\sum\limits_{k=1}^n k{\Large)}^2$ without induction

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.

Thanks!

-
Look at this takayaiwamoto.com/Sums_and_Series/sumcube_1.html –  pritam Jun 27 '12 at 9:29
See math.stackexchange.com/questions/120674 for remarks about proofs "not using induction". –  sdcvvc Jun 27 '12 at 10:13
I merged the three existing posts which covered exactly this question, as each post had different interesting answers which should not be lost. I also deleted redundant comments, and comments about closing posts as duplicates. This fourth question is not considered a duplicate. –  Eric Naslund Jul 2 '12 at 11:30
Since this question is asked frequently, it has been added to the list of Generalizations of Common questions. It has been kept seperate from the version which does use induction. –  Eric Naslund Aug 30 '12 at 0:23
show 1 more comment

Stare at the following image, taken from this MO answer, long enough:

-
+1 I'm in love with that one –  leonbloy Sep 2 '11 at 23:23
The fact that there are $k$ blocks (or $\frac{1}{2}+k{-}1+\frac{1}{2}$ blocks) of $k\times k$ size is based on the fact that $\sum\limits_{j=1}^{k-1}=k(k{-}1)/2$. That is, $(k{-}1)/2$ blocks on top $(k{-}1)/2$ on the left and $1$ block at the corner (totaling to $k$). Perhaps I am being picky or slow, but I don't see this as obvious from the image. Beyond that, it is a nice proof-without-words. –  robjohn Sep 3 '11 at 4:13
I have put the details of the proof corresponding to this image in this answer since the comment area was too small. –  Wok Sep 3 '11 at 7:23

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$

-
If we forget the first line of the matrix (which is zero and which is only used to make pairs with the diagonal coefficients), then I like the fact we can put this answer in parallel with the coloured rectangles above and below, and we get another partition of each colored area (each coefficient of the matrix gives a rectangle of a certain area), which explains why each L-shaped area is $k^3$. –  Wok Sep 4 '11 at 7:39
However, each L-shape coefficient has the same factor $k$, which means it proves "each L-shaped area is $k^3$" by the same proof that $2 \times \sum_{j=0}^k j = (0+k) + (1+k-1) + ... + (k-1+1) + (k+0) = (k+1) \times k$, which makes it really close to the coloured rectangles above and below. –  Wok Sep 4 '11 at 7:49
I hope you don't mind if I use both ideas in another answer. –  Wok Sep 4 '11 at 8:13
I don't mind. I simply find it less aesthetic to need to use $\sum\limits_{j=1}^k\;j=k(k+1)/2$ or that $(k(k+1)/2)^2-(k(k-1)/2)^2=k^3$ in an intuitive proof. –  robjohn Sep 4 '11 at 19:31

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.

-
nice, but already posted (linked) by Mariano –  leonbloy Sep 2 '11 at 23:24

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.

-

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$$

-
So essentially, you are using the fact that $$\left(\sum_{j=1}^k\;j\right)^2-\left(\sum_{j=1}^{k-1}\;j\right)^2=k^3$$ to justify the diagram which is supposed to prove that fact intuitively. –  robjohn Sep 4 '11 at 1:09
As you mentioned in another answer, this is where the diagram is the least intuitive. However, if you cannot picture $k^3$ on a 2D-plane, then you need another representation as a difference of areas. –  Wok Sep 4 '11 at 6:50
As soon as you know $S_k = \sum_{j=1}^k j = \frac{k(k+1)}{2}$, I find it more intuitive to figure out each colored area is $k^3$ on this diagram than to figure it out by counting squares plus two rectangles when $k$ is even. –  Wok Sep 4 '11 at 7:06

The formula is due to Nicomachus of Gerasa. There is a nice discussion of ways to prove it at this n-category cafe post, including a bijective proof and some visual / "geometric" proofs.

-

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$.

-

I found this but sadly do not understand it, can someone explain the method?

Edit:

This has the same proof but much easier to understand. It is also found in the link by QY

-
Excellent picture!! (second one) –  Eric Naslund Jan 22 '11 at 20:14

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:

• 84 Mathematical Gazette, vol. 49, no. 368 (May 1965), p. 199. jstor
• 85 Mathematics Magazine, vol. 50, no. 2 (March 1977), p. 74. jstor
• 86 Mathematics Magazine, vol. 58, no. 1 (Jan. 1985), p. 11. jstor
• 87 Mathematics Magazine, vol. 62, no. 4 (Oct. 1989), p. 259. jstor
• 87 Mathematical Gazette, vol. 49, no. 368 (May 1965), p. 200. jstor
• 88 Mathematics Magazine, vol. 63, no. 3 (June 1990), p. 178. jstor
• 89 Mathematics Magazine, vol. 62, no. 5 (Dec. 1989), p. 323. jstor
• 90 Mathematics Magazine, vol. 65, no. 3 (June 1992), p. 185. jstor
-
Great collections. Thanks –  B. S. Jun 27 '12 at 11:11

I believe this illustration is due to Anders Kaseorg:

-

We know that $$A=\Sigma_{1}^{n}k^3=\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2$$ and $$B=\Sigma_{1}^{n}k=\frac{1}{2}n^2+\frac{1}{2}n$$ $A-B^2=0$. :)

-
If you are presenting this proof,write it nicely. $A=\frac{n^2(n+1)^2}{4}$ and $B=\frac{n(n+1)}{2}$,obviously $A=B^2$ –  Aang Jun 27 '12 at 10:40
@avatar: Dear Avatar; I will. Your proof is great and it looks analytically. Thanks. :-) –  B. S. Jun 27 '12 at 10:48
sorry, if you felt that i was being rude. –  Aang Jun 27 '12 at 10:53
@avatar: Your proof lights mine. No Problem at all. WELCOME Avatar. :) :) –  B. S. Jun 27 '12 at 10:57

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)$.

-

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 $(\lim_{x\to1}\frac{x^n(nx-n-1)+1}{x^2-2x+1})^2$. You can also prove it using telescopic series.

-
why does the assumption hold? this is usually proved using induction... –  akkkk Jun 27 '12 at 9:47
what assumption?? –  Aang Jun 27 '12 at 9:48
I guess Auke means $\sum_{0}^{n} x^k=\frac{1-x^{n+1}}{1-x}$. –  sdcvvc Jun 27 '12 at 10:12
LHS is a geometric series. en.wikipedia.org/wiki/Geometric_progression –  Aang Jun 27 '12 at 10:14
@Auke: one can also prove it like this - let $f(x) = \sum\limits_{k=0}^nx^k$, then $f(x) - xf(x)$ is: \begin{align} 1+&x+x^2+\dots+x^n \\ &- \\ &x+x^2+\dots+x^n+x^{n+1} \end{align} which is $1-x^{n+1}$. Hence $$(1-x)f(x) = 1-x^{n+1}$$ as needed. –  Ilya Jun 27 '12 at 12:40

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.

-
And $a$ is always a factor of $p$. –  lhf Sep 3 '11 at 13:26

http://blogs.mathworks.com/loren/2010/03/04/nichomachuss-theorem/

-

$f(n)=1^3+2^3+3^3+......+n^3$

$f(n-1)=1^3+2^3+3^3+......+(n-1)^3$

$f(n)-f(n-1)=n^3$

if $f(n)= (1+2+3+4+....+n)^2$ then

$$f(n)-f(n-1)=(1+2+3+4+....+n)^2-(1+2+3+4+....+(n-1))^2$$

using $a^2-b^2=(a+b)(a-b)$

$f(n)-f(n-1)=$

$=[1+1+2+2+3+3+4+4+....+(n-1)+(n-1)+n][1-1+2-2+3-3+4-4+....+(n-1)-(n-1)+n]=$

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

-
This is about the same proof as here, the presentation is a bit different though. This is another way to make $k^3$ appear than what was shown here, here and here.