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

What reason or hint would there be that $$\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$$

Every combinatoric proof I have seen, seemed quite intuitive with the equation already giving hints to how to prove it. This statement above however does not seem logical. Although algebraically it does work out. My question specific:

What does the left side mean? How would you interpret it combinatorially?

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.$$