Prueba combinatoria de $\sum_{1\le i\le n,\ 1\le j\le n}\min(i,j)=\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6$

Question

¿% #% $ De #% existe un vínculo entre estas dos cantidades idénticas?

Answer 1

Mira un $n\times n$ matriz cuya entrada en la fila $i$ y la columna $j$$\min\{i,j\}$:

$$\begin{array}{ccc} 1&1&1&1&\ldots&1\\ 1&2&2&2&\ldots&2\\ 1&2&3&3&\ldots&3\\ 1&2&3&4&\ldots&4\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&2&3&4&\ldots&n \end{array}$$

Las entradas en la primera columna y la fila superior se $1$. Si usted tira de los de fuera, las entradas en la primera columna y la primera fila de lo que queda son las $2$. Si usted tira de los de fuera, las entradas en la primera columna y la primera fila de lo que queda son las $3$, y así sucesivamente.

Ahora piensa en esto como una representación de la parte superior de la vista de los objetos de tres dimensiones hecho de $1\times1\times 1$ bloques en los que el número en una celda representa la altura del objeto en ese punto; el objeto es una especie de pirámide escalonada que alcanza una altura de $n$ en el inferior de la esquina derecha. La capa inferior contiene $n^2$ bloques. La segunda capa contiene $(n-1)^2$. Y en general el $k$-ésima capa contiene $(n+1-k)^2$ bloques, por lo que el número total de bloques (y por lo tanto la suma de las entradas de la matriz) es

$$\sum_{k=1}^n(n+1-k)^2=\sum_{k=1}^nk^2\;.$$

Answer 2

No estoy seguro si esto es lo que buscas:

Answer 3

No estoy seguro de si esta es la interpretación correcta de la pregunta, pero suponiendo que el OP quiere una prueba de la igualdad de la identidad, aquí hay una prueba. Tenga en cuenta que$$\sum_{1\le i\le n,\ 1\le j\le n}\min(i,j)=\sum_{i=1}^n \sum_{j=1}^{i}\min(i,j)+\sum_{i=1}^n \sum_{j=i+1}^{n}\min(i,j)\\=\sum_{i=1}^n\sum_{j=1}^{i}j+\sum_{i=1}^n \sum_{j=i+1}^{n}i\\=\sum_{i=1}^n \frac{i(i+1)}{2}+\sum_{i=1}^n i(n-i)\\=\left(n+\frac{1}{2}\right)\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{12}\\=\frac{n(n+1)(2n+1)}{6}=\sum_{i=1}^ni^2 $ $

Answer 4

Para la segunda igualdad, aviso que $\frac{n(n+1)(2n+1)}6=\binom{n+1}{2} + 2 \binom{n+1}{3}$. Ambos lados contar el número de ordenadas triples $(i,j,k)(i,j,k)$$0≤i,j<k≤n$.
Para un determinado $k$ hay $k^2$ formas eligió $i$$j$$\{0, 1, \ldots, k-1\}$. Es el lado izquierdo.
Considerar los casos de $i=j$ $i \neq j$ por separado. Si $i = j$, entonces no se $\binom{n+1}{2}$ tal triples. Tenemos dos números de $\{0, \ldots, n\}$; el menor debe ser el valor de $i$ $j$ y el más grande debe ser el valor de $k$. Si $i \neq j$, entonces no se $2\binom{n+1}{3}$ tal triples, como podríamos haber $i < j$ o $j < i$ para los más pequeños de dos números.
Por lo tanto $\sum_{i=1}^ni^2=\binom{n+1}{2} + 2 \binom{n+1}{3}=\frac{n(n+1)(2n+1)}6$

Para la primera igualdad de (el uso de la segunda): $$\sum_{1\le i\le n,\ 1\le j\le n}\min(i,j)=\sum_{1\le i\le n}(\sum_{\ 1\le j\le i-1}\min(i,j)+\sum_{\ i\le j\le n}\min(i,j))=\sum_{1\le i\le n}(\sum_{\ 1\le j\le i-1}j+\sum_{\ i\le j\le n}i)=\sum_{1\le i\le n}(\frac{i(i-1)}{2}+i(n-i+1))=\sum_{1\le i\le n}\frac{i^2-i+2in-2i^2+2i}{2}\\=\sum_{1\le i\le n}\frac{-i^2+(2n+1)i}{2}=-\frac{1}{2}\sum_{i=1}^ni^2+\frac{2n+1}{2}\frac{n(n+1)}{2}\\=-\frac{1}{2}\sum_{i=1}^ni^2+\frac{3}{2}\frac{n(n+1)(2n+1)}6=\sum_{i=1}^ni^2$$

Answer 5

$$ \begin{array}{rr|rrrrrrr} \hline \min(i,j)&&i\\ &&1&2&3&4&\cdots &(n-2)&(n-1)&n\\ \hline j&1&1&1&1&1&\cdots &1&1&1\\ &2&1&2&2&2&\cdots &2&2&2\\ &3&1&2&3&3&\cdots &3&3&3\\ &4&1&2&3&4&\cdots &4&4&4\\ &\vdots&&&&&\ddots \\ &\vdots \\ &\vdots \\ &(n-2)&1&2&3&4&&\color{green}{(n-2)}&\color{green}{(n-2)}&\color{green}{(n-2)}\\ &(n-1)&1&2&3&4&&\color{green}{(n-2)}&\color{blue}{(n-1)}&\color{blue}{(n-1)}\\ &n&1&2&3&4&&\color{green}{(n-2)}&\color{blue}{(n-1)}&\color{red}n\\ \hline \end {array} $$

De la tabla anterior, está claro que $$ \begin{align} \sum_{1\le i,j\le n}\min(i,j) &=\color{red}{1\cdot n}+\color{blue}{3\cdot (n-1)}+\color{green}{5\cdot (n-2)}+\cdots+(2n-1)\cdot 1 \\ &=\sum_{r=1}^n (2r-1)\color{orange}{(n+1-r)}\\ &=\sum_{r=1}^n \color{orange}{\sum_{i=r}^n}(2r-1)\\ &=\sum_{i=1}^n\sum_{r=1}^i (2r-1) \color{lightgrey}{=\sum_{i=1}^n\sum_{r=1}^i r^2-(r-1)^2}\\ &=\sum_{i=1}^n i^2\quad\blacksquare\\ \end {align} $$