11
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

12
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Okay thank you. it's brilliant! The crux for me was, that you both allow x and y to be 0, but you do not allow z to be 0 $\endgroup$
    – Rich_Rich
    Feb 14, 2019 at 21:46
  • $\begingroup$ Essentially, this combinatorializes the combination of the identity $k^2=\binom{k}{2}+\binom{k+1}{2}$ and the hockey stick identity. $\endgroup$ Oct 13, 2023 at 2:58
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I must be missing something obvious... For part 1, I can understand the first equality but not the second. Pls explain? $\endgroup$
    – antkam
    Nov 8, 2019 at 14:45
  • $\begingroup$ @antkam The second equality follows from the combinatorial identity $$\binom12+\binom22+\cdots+\binom{n-1}2+\binom n2=\binom{n+1}3.$$ $\endgroup$
    – bof
    Nov 9, 2019 at 0:47
  • $\begingroup$ Ah, and that identity follows from considering how to pick e.g. the largest element in choosing $3$ elements from $n+1$. Got it. Thanks! $\endgroup$
    – antkam
    Nov 9, 2019 at 0:50
  • $\begingroup$ @antkam $\binom{n+1}3$ is the number of integer triples $x\lt y\lt z$ with $0\le x\lt y\lt z\le n$, and $\binom k2$ is the number of such triples with $z=k$. $\endgroup$
    – bof
    Nov 9, 2019 at 0:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .