Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Why stop at this point? A little bit of a hard work and you will be done. :-) –  Srivatsan Nov 1 '11 at 4:36
2  
@Salazar Nice going. You will find this earlier question interesting. –  Sasha Nov 1 '11 at 4:39
2  
@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
2  
@Emmad Have you seen this earlier question of Salazar? –  Srivatsan Nov 1 '11 at 6:17

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.