Seeking a combinatorial proof of the identity $1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$

Question

I would appreciate if somebody could help me with the following problem

Q: show that combinatoric identity (using by combinatorial proof) $$1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$$

Answer 1

I (think) this solution is from Proofs that Really Count. I might be mis-attributing it, but either way it is a great book.

---

Consider the ordered pair $(a, b, c, d)$ with $0 \le a, b, c < d \le n$. The number of solutions is:

$$ \sum_{d=1}^n d^3$$

Since after choosing $d$, we have $d^3$ choices for $(a, b, c)$.

Then consider $(e, f)$ and $(g, h)$, with $0 \le e< f \le n$ and $0 \le g < h \le n$. There are ${n+1 \choose 2}^2$ choices.

Bijection: If $a < b$, map $(a, b, c, d)$ to $(a, b)$, $(c,d)$. If $b > a$ then map $(a, b, c, d)$ to $(a, d)$, $(c, d)$. Lastly, if $a = b$, map $(a, b, c, d)$ to $(b, d)$, $(c, d)$. This can be reversed, and it covers all three cases of $a > b$, $a = b$ and $a < b$.

Answer 2

HINT

Count the number of rectangles in a $n$ by $n$ chessboard in two different ways.

Move your mouse over the gray area for a complete solution.

A rectangle is formed by two vertical lines and two horizontal lines. Hence, the number of ways of choosing $n$ vertical lines is $\dbinom{n+1}2$ and the number of ways of choosing $n$ horizontal lines is $\dbinom{n+1}2$. Hence, the number of rectangles is $$\left(\dbinom{n+1}2 \right)^2$$ Lets count the number of rectangles in another way. Consider a $m \times m$ square with left bottom at $(0,0)$ and right top at $(m,m)$ and $m \leq n$. We will count the number of rectangle, which falls inside the square and the top right vertex lies on $x=m$ or $y=m$. If the right vertex is at $x=m$ and $y=d$, the number of rectangles is $md$. Similarly, if the right vertex is at $x=d$ and $y=m$, the number of rectangles is $md$. If the right vertex lies at $(m,m)$, the number of rectangles is $m^2$. Hence, the total number of rectangles is $$m^2 +\sum_{d=1}^{m-1} md + \sum_{d=1}^{m-1} md = m^2 +2m \dfrac{m(m-1)}2 = m^3$$ Now let $m$ run from $1$ to $n$, to get the total number of rectangles as$$\sum_{m=1}^n m^3$$