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

binomial-coefficientscombinatoricssummation

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.

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.