Combinatorial proof of $\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$

Consider trying to count ordered triples $(x,y,z)$ of integers where

• $0\le x< z$

• $0\le y< z$

• $1\le z\le n$

When $z=k$, there are $k$ choices for $x$ and $k$ choices for $y$, so the number of triples is indeed $\sum_{k=1}^nk^2$.

Alternatively, let us take all triples where $x<y$ and identify them with the subset $\{x,y,z\}$ of $\{0,1,2,\dots,n\}$. There are $\binom{n+1}3$ such subsets, each uniquely representing a triple where $x<y$.

The only remaining triples are the ones where $x\ge y$. Associate each such triple $(x,y,z)$ to the subset $\{y,x+1,z+1\}$ of $\{0,1,2,\dots,n+1\}$. There are $\binom{n+2}3 $ such subsets, each again uniquely representing a triple where $x\ge y$. The triple corresponding to $\{a<b<c\}$ is $(b-1,a,c-1)$.

The following combinatorial proof is copied from my answer to this question.

Let $B_n$ denote the number of ways you can place two white bishops on an $n\times n$ chessboard so that they guard each other, i.e., they lie on a diagonal of the chess board. I will evaluate $B_n$ in two different ways.

I. There are $2n-1$ diagonals of positive slope, of lengths $1,2,\dots,n-1,n,n-1,\dots,2,1$, and the same goes for diagonals of negative slope. The number of ways to choose a diagonal and then place two bishops on that diagonal is $$B_n=2\left[\binom12+\cdots+\binom{n-1}2+\binom n2+\binom{n-1}2+\cdots+\binom12\right]=2\binom{n+1}3+2\binom n3.$$

II. A pair of bishops guard each other iff they are at opposite corners of a $k\times k$ square for some $k\ge2$. Since the number of $k\times k$ squares in an $n\times n$ chessboard is $(n-k+1)^2$, and each square has two pairs of opposite corners, we have $$B_n=2\left[(n-1)^2+\cdots+2^2+1^2\right].$$
Equating the two expressions for $B_n$ and dividing to $2$, we have $$1^2+2^2+\cdots+(n-1)^2=\binom n3+\binom{n+1}3$$ or, substituting $n+1$ for $n$, $$1^2+2^2+\cdots+n^2=\binom{n+1}3+\binom{n+2}3.$$