# Summation Identity: $\sum_{i=1}^ni^3 = \left( \frac{n(n+1)}{2} \right)^2$

I have to prove:

$$\sum\limits_{i = 1}^n i^3 = \Bigg( \frac{n(n+1)}{2}\Bigg)^2$$

Using the following:

$$n^3 = 6 {n \choose 3} + 6 {n \choose 2} + n \quad \forall n \in \mathbb{N}$$

My work is that first I substitute $n^3$ for $6 {n \choose 3} + 6 {n \choose 2} + n$. Then I go and invoke the sum over that (I am assuming this is how it works). That is,

$$\sum\limits^n_{i=1} \bigg(6 {i \choose 3} + 6 {i \choose 2} + i \bigg)$$

$$6 \sum\limits^n_{i=1} {i \choose 3} + 6 \sum\limits^n_{i=1} {i \choose 2} + \sum\limits^n_{i=1} {i \choose 1}$$

The summation identity is:

$$\sum\limits^n_{i=0} {i \choose k} = {n+1 \choose k+1}$$ invoking it over the sums yields:

$$6{n+1 \choose 4} + 6{n+1 \choose 3} + {n+1 \choose 2}$$

I think these are the right steps, but simplification seems a bit difficult to get the ending result.

-
Why stop at this point? A little bit of a hard work and you will be done. :-) –  Srivatsan Nov 1 '11 at 4:36
@Salazar Nice going. You will find this earlier question interesting. –  Sasha Nov 1 '11 at 4:39
@Salazar Simplification is quite simple by noticing $\binom{n+1}{4} = \frac{n-2}{4} \binom{n+1}{3}$ and $\binom{n+1}{3} = \frac{n-1}{3} \binom{n+1}{2}$. –  Sasha Nov 1 '11 at 4:42
I would like to know more about $n^3 = 6 {n \choose 3} + 6 {n \choose 2} + n \quad \forall n \in \mathbb{N}$ - Could some one post a reference? –  Emmad Kareem Nov 1 '11 at 5:55
@Emmad Have you seen this earlier question of Salazar? –  Srivatsan Nov 1 '11 at 6:17

It’s just algebra $-$ tedious, but straightforward:

\begin{align*} 6\binom{n+1}4&+6\binom{n+1}3+\binom{n+1}2\\ \strut\\ &=\frac{6(n+1)n(n-1)(n-2)}{4!}+\frac{6(n+1)n(n-1)}{3!}+\frac{(n+1)n}2\\ &=n(n+1)\left(\frac{(n-1)(n-2)}{4}+(n-1)+\frac12\right)\\ &=\frac{n(n+1)}4\big((n-1)(n-2)+4(n-1)+2\big)\\ &=\frac{n(n+1)}4\big((n-1)(n+2)+2\big)\\ &=\frac{n(n+1)}4(n^2+n)\\ &=\frac{n^2(n+1)^2}4\\ &=\left(\frac{n(n+1)}2\right)^2 \end{align*}

-

Suppose we have arrived at the expression $$6{n+1 \choose 4} + 6{n+1 \choose 3} + {n+1 \choose 2},$$ and we remain in a combinatorial mood, not an algebraic one. Then we might work a little harder and give a bijective argument.

From a group of $n+1$ boys and $n+1$ girls, we can choose $2$ boys and $2$ girls (a pair of pairs) in $$\binom{n+1}{2}^2$$ ways. We will count the number of pairs of pairs in another way.

Let the boys be called $b_0,b_1,\dots,b_n$, and the girls $g_0, g_1,\dots,g_n$. If $2$ boys and $2$ girls are chosen they either (a) share no number or (b) share $1$ number or (c) share $2$ numbers.

(a) The pairs of pairs that share no number can be chosen as follows. Choose $4$ numbers from the set $\{0,1,\dots,n\}$. Then choose $2$ of the $4$ numbers, and select the boys with these $2$ numbers, and the girls with the remaining $2$ numbers. The choosing of $4$ numbers can be done in $\binom{n+1}{4}$ ways, and the choosing of $2$ from $4$ can be done in $\binom{4}{2}=6$ ways, for a total of $$6\binom{n+1}{4}.$$

(b) The pairs of pairs that share exactly one number can be chosen as follows. Choose $3$ numbers from $\{0,1,\dots,n\}$. Choose $1$ of these $3$ numbers to be the "duplicated" number (boy and girl), then select the boy who has $1$ of the remaining numbers, and the girl with the other. The choosing of the $3$ numbers can be done in $\binom{n+1}{3}$ ways. For each of these, we can choose the duplicated number in $3$ ways, and decide which of the remaining numbers will be a boy number in $2$ ways, for a total of $$(3)(2)\binom{n+1}{3}.$$

(c) Finally, we count the pairs of pairs that share two numbers. All we need to do is to choose these $2$ numbers, and the rest is determined, so the number of type (c) pairs of pairs is $$\binom{n+1}{2}.$$ Add up.

-
Very interesting! –  Emmad Kareem Nov 1 '11 at 5:44
It really should not be boys and girls, better two rows of $n+1$ seats, one row behind the other, and we want to choose $2$ seats in each row. Or some other concrete situation. Counting is much easier if you can visualize. –  André Nicolas Nov 1 '11 at 5:51

Don't stop, just do! =) $$\begin{eqnarray*} && 6 \binom{n+1}{4} + 6\binom{n+1}{3} + \binom{n+1}{2} \\ &=& 6 \frac{(n+1) n (n-1)(n-2)}{24} + 6 \frac{(n+1) n (n-1)}{6} + \frac{(n+1) n}{2} \\ &=& \frac{n(n+1)}{4} \left( (n-1)(n-2) + 4 (n-1) + 2 \right) \\ &=& \cdots \end{eqnarray*}$$ I presume you can simplify the expression further to get the right hand side.

-