Combinatorial interpretation of sum of squares, cubes
Here's a combinatorial proof for $$\sum_{k=1}^n k^2 = \binom{n+1}{2} + 2 \binom{n+1}{3},$$ which is just another way of expressing the sum. Both sides count the number of ordered triples $(i,j,k)$ with $0 \leq i,j < k \leq n$.
For the left side, condition on the value of $k$. For each $k$, there are $k^2$ ways to choose $i$ and $j$ from the the set $\{0, 1, \ldots, k-1\}$.
For the right side, consider the cases $i=j$ and $i \neq j$ separately. If $i = j$, then there are $\binom{n+1}{2}$ such triples. This is because we just choose two numbers from $\{0, \ldots, n\}$; the smaller must be the value of $i$ and $j$ and the larger must be the value of $k$. If $i \neq j$, then there are $2\binom{n+1}{3}$ such triples, as we could have $i < j$ or $j < i$ for the smaller two numbers.
For $$\sum_{k=1}^n k^3 = \binom{n+1}{2}^2,$$ both sides count the number of ordered 4-tuples $(h,i,j,k)$ with $0 \leq h,i,j < k \leq n$.
For the left side, once again if we condition on the value of $k$ we see that there are $\sum_{k=1}^n k^3$ such 4-tuples.
For the right side, there is a bijection from these 4-tuples to ordered pairs of two-tuples $(x_1,x_2), (x_3,x_4)$ with $0 \leq x_1 < x_2 \leq n$ and $0 \leq x_3 < x_4 \leq n$. There are $\binom{n+1}{2}^2$ such pairs, so let's look at the bijection.
The bijection: If $h < i$, then map $(h,i,j,k)$ to $(h,i),(j,k)$. If $h > i$, then map $(h,i,j,k)$ to $(j,k), (i,h)$. If $h = i$, then map $(h,i,j,k)$ to $(i,k), (j,k)$. This mapping is reversible, as these three cases correspond to the cases where $x_2 < x_4$, $x_2 > x_4$, and $x_2 = x_4$.
(Both of these proofs are in Chapter 8 of Proofs that Really Count, by Benjamin and Quinn. They give at least one other combinatorial proof for each of these identities as well.)
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)]$.