<s>[INST] Combinatorial interpretation of sum of squares, cubes Consider the sum of the first $n$ integers:
$$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$
This makes the following bit of combinatorial sense.  Imagine the set $\{*,1,2,\ldots,n\}$.  We can choose two from this set, order them in decreasing order and thereby obtain a point in $\mathbb{N}^2$.  We interpret $(i,*)$ as $(i,i)$.  These points give a clear graphical representation of $1+2+\cdots+n$:
$$
\begin{matrix}
&&&\circ\\
&&\circ&\circ\\
&\circ&\circ&\circ\\
\circ&\circ&\circ&\circ\\
\end{matrix}
$$
Similar identities are:
$$\sum_{i=1}^n\,i^2=\frac{1}{4}\binom{2n+2}{3}=\frac{1}{2n-1}\binom{2n+2}{4}=\frac{1}{2n+3}\binom{2n+3}{4}$$
$$\sum_{i=1}^n\,i^3=\binom{n+1}{2}^2$$
I am aware of geometric explanations of these identities, but not combinatorial ones similar to the above explanation for summing first powers that make direct use of the "choosing" interpretation of the binomial coefficient.  Can anyone offer combinatorial proofs of these?
 [/INST] We give a combinatorial interpretation of the formula
$$
2^2+4^2+6^2+\cdots +(2n)^2=\binom{2n+2}{3} \qquad\qquad (1)
$$
for the sum of the first $n$ even squares.
There are  $\binom{2n+2}{3}$ ways to choose $3$ numbers from the numbers $1, 2, \dots, 2n+2$. We organize and count the choices in another way.
Maybe the largest number chosen is $2k+1$ or $2k+2$. If it is $2k+1$, the other two can be chosen in $\binom{2k}{2}$ ways, and if it is $2k+2$, then the other two can be chosen in $\binom{2k+1}{2}$ ways.  The total is
 $$\frac{(2k)(2k-1)}{2} +\frac{(2k+1)(2k)}{2}\quad\text{that is,}\quad (2k)^2.\qquad\qquad(2)$$
 Take $k=1, 2, 3, \dots, n$.  By Formula $(2)$, the number of ways of choosing $3$ numbers from $1, 2, \dots, 2n+2$ is 
$$
2^2+4^2+6^2+\cdots +(2n)^2.
$$
The above argument was not purely bijective, because of the ``calculation'' in Formula $(2)$.  But there is a standard workaround that produces a purely bijective proof of the fact that
 $$
 \binom{m}{2} +\binom{m+1}{2}=m^2.
$$
The geometric idea is that the sum of two consecutive triangular numbers is a square. More formally, let $M$ be the collection $\{1,2,3,\dots,m\}$. Then the number of  ordered pairs $(a,b)$ with $a$ and $b$ in $M$ is $m^2$.  These ordered pairs are of two types: (i) the ones with $a<b$ and (ii) the ones with $a \ge b$. The number of ordered pairs $(a,b)$ with $a<b$ is just $\binom{m}{2}$.  The number of ordered pairs $(a,b)$ with $a \ge b$ is the same as the number of ordered pairs $(b,a+1)$ with $b<a+1$, and this is $\binom{m+1}{2}$.  
Comment: 
It follows by "algebra" from Formula $(1)$ that
$$
1^2+2^2+\cdots +n^2=\frac{1}{4}\binom{2n+2}{3}. \qquad\qquad(3)
$$
(The algebraic division by $4$ can be bypassed by counting suitable equivalence classes, giving a pristinely bijective proof of $(3)$.)
When I first saw the usual expression $\dfrac{(n)(n+1)(2n+1)}{6}$ for the sum of the first $n$ squares, I remember thinking that the $2n+1$ somehow looks as if it does not fit in. But it does, it is actually $n$ and $n+1$ that are strange!  We can think of $(n)(n+1)(2n+1)$ as ``really'' being $(1/4)[(2n)(2n+1)(2n+2)]$.  
</s>