Una Combinatoria prueba de la identidad de $\sum_i \sum_j \min(i,j) = \sum_k k^2$

Question

Tengo que probar esto (un combinatorally la prueba, contando con un conjunto de dos maneras diferentes):

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

Esto es lo que he hecho: tomar el conjunto $$\{(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.$$ Pero no puedo formalizar que, me podrían ayudar por favor?

Answer 1

Usted podría tratar de una recursividad. Si $L(n)$ es el lado izquierdo, lo que es $L(n+1) - L(n)$?

Su observación hace un buen "prueba sin palabras", aunque.

Answer 2

Usted podría visualizar como esta. Empezar con un $n \times n$ cuadrados divididos en $n^2$ unidad de plazas. La etiqueta de las filas y las columnas $1$ a través de $n$. Ahora imagine que usted tiene un montón de cúbico de bloques de una unidad de lado. En la unidad de la plaza en la fila $i$ columna $j$ la pila de $\min\{i,j\}$ de estos bloques. Es evidente que esto requiere de $\sum_{i=1}^n \sum_{j=1}^n \min\{i,j\}$ bloques.

Para llegar al otro lado de la identidad, el recuento de los bloques por capas. Hay claramente $n^2$ bloques en la capa uno, en la parte inferior. La columna de los bloques de la fila $i$ columna $j$ que llega a la capa de $k$ si y sólo si $k \le \min\{i,j\}$, lo cual es cierto si y sólo si $k \le i$ e $k \le j$, es decir, $i,j \ge k$. El número de células en el original de la cuadrícula de satisfacciones $i,j \ge k$$[n-(k-1)]^2$, de modo de contar por capas da un total de $$\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$$ bloques.