# A Combinatorial proof for the identity $\sum_i \sum_j \min(i,j) = \sum_k k^2$

I have to prove this (a combinatorally proof, counting a set in two different ways):

$$\sum_{i=1}^n\sum_{j=1}^n\mathrm{min}(i,j)=\sum_{k=1}^nk^2 .$$

This is what I have done: take the set $$\{(x_1,x_2,x_3)\in\mathbb{Z}^3:1\leq x_1, x_2 \leq k, x_3=k, k=1,\ldots,n\}.$$ This set consists of $n$ squares with increasing side. I noticed that if you count the set adding the points diagonally square by square, you get the formula with the minimum. I mean if $n=3$, then the diagonals with $1$ point are $5$, the diagonals with $2$ points are $3$ and the diagonal with $3$ points is $1$, so you have $$1+1+1+1+1+2+2+2+3.$$ But I can't formalize that, could you help me please?

-

You could visualize it like this. Start with an $n \times n$ square divided into $n^2$ unit squares. Label the rows and the columns $1$ through $n$. Now imagine that you have a bunch of cubical blocks one unit on a side. On the unit square in row $i$, column $j$ you stack $\min\{i,j\}$ of these blocks. Clearly this requires $\sum_{i=1}^n \sum_{j=1}^n \min\{i,j\}$ blocks.

To get the other side of the identity, count the blocks by layers. There are clearly $n^2$ blocks in layer one, at the bottom. The column of blocks in row $i$, column $j$ reaches up to layer $k$ if and only if $k \le \min\{i,j\}$, which is true if and only if $k \le i$ and $k \le j$, i.e., $i,j \ge k$. The number of cells in the original grid satisfying $i,j \ge k$ is $[n-(k-1)]^2$ so counting by layers gives a total of $$\sum\limits_{k=1}^n [n-(k-1)]^2 = \sum\limits_{k=0}^{n-1} (n-k)^2 = \sum\limits_{k=1}^n k^2$$ blocks.

-
You could try a recursion. If $L(n)$ is the left side, what is $L(n+1) - L(n)$?