¿Cómo se demuestra la igualdad de estos dos sumatorias?

Question

¿Cómo se puede mostrar el siguiente? $$\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1 = \sum \limits_{j=1}^{n}\ \sum \limits_{k=1}^{j}\ \sum \limits_{i=1}^{k}\ 1 $$ No es obvio por qué esto es cierto, pero lo he probado con un programa y funciona.

Answer 1

Esta parece una muy buena excusa para cambiar a Iverson soportes. Dejando $[p]$ $1$ si $p$ es cierto, y $0$ si $p$ es falso, podemos expresar la suma de la izquierda como

$$\sum_i\sum_j\sum_k [1 \leq i \leq n][i \leq j \leq n][i \leq k \leq j]$$

donde la suma se toma sobre todos los $i,j,k$. Esto puede ser tomado justamente como un infinito triple de series de términos no negativos: la Iverson soportes de asegurarse de que los términos que no estaban presentes en el original de la serie están muy bien poner a cero.

Utilizando el hecho de que $[p][q]=[p\text{ and }q]$, tenemos el equivalente de la expresión

$$\sum_i\sum_j\sum_k [1\leq i\leq k\leq j\leq n]=\sum_j\sum_k\sum_i [1\leq i\leq k\leq j\leq n]$$

donde éramos libres para permutar el orden de la suma.

Podemos pelar lentamente Iverson factores como así:

$$\begin{align*}\sum_j\sum_k\sum_i [1\leq i\leq k\leq j\leq n]&=\sum_j\sum_k\sum_i [1\leq i\leq k][1\leq k\leq j\leq n]\\&=\sum_j\sum_k\sum_i [1\leq i\leq k][1\leq k\leq j][1\leq j\leq n]\\&=\sum_j[1\leq j\leq n]\sum_k[1\leq k\leq j]\sum_i [1\leq i\leq k]\end{align*}$$

y la última expresión es precisamente la suma de la derecha, reescrito en Iversonian forma.

Answer 2

Ambas cuentan la cardinalidad del conjunto $\{ (i, j, k) \in \mathbb Z^3 \mid 1 \leq i \leq k \leq j \leq n \}$.

Explicación. Tratamos de contar el conjunto de $$ S := \{ (i, j, k) \in \mathbb Z^3 \mid 1 \leq i \leq k \leq j \leq n \} $$ de dos maneras.

Lado derecho.

1. La primera revisión el elemento más grande de la triple, a saber,$j$; esto puede tomar los valores de $1$$n$. Luego solucionamos $k$$i$, en ese orden.

2. Para cualquier valor dado de a $j$, la variable $k$ puede tomar los valores de $1$ $j$(ya sabemos que $1 \leq k \leq j$).

3. Dado que los valores de$k$$j$, la variable $i$ puede tomar los valores de $1$ hasta los más pequeños de $k$$j$, es decir, $k$ (ya sabemos que $i \leq k$$i \leq j$).

Se puede ver cómo el lado derecho de la expresión corresponde a la explicación anterior?

A mano izquierda. Adoptamos una estrategia similar de la fijación de los valores de las variables de una en una. Pero esta vez, se corrige en el orden de la $i, j, k$.

1. Como antes, $i$ toma los valores de$1$$n$.

2. Una vez que hemos fijado el valor de $i$, es claro que $j$ toma los valores de$i$$n$.

3. Dado que los valores de$i$$j$, la variable $k$ toma valores en el rango de $[i, j]$.

Si usted escribe esto en términos de la notación de sumatoria, no ves la forma de sacar el lado izquierdo?

Answer 3

Mi respuesta no es matemáticamente riguroso, sino que debe ayudar en la visualización de las otras soluciones. Primero de todo, sin pérdida de generalidad, la indexación de la mano derecha puede ser cambiado para que coincida con el lado izquierdo de la siguiente manera:

$$\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1 = \sum \limits_{i=1}^{n}\ \sum \limits_{j=1}^{i}\ \sum \limits_{k=1}^{j}\ 1$$

Ahora la diferencia radica en dos interior sumatorias, que puede ser mostrado como zonas rojas en la izquierda y la derecha, respectivamente, en la imagen de abajo. (Perdón por mi dibujo rápido.)

De$i = 1$$n$, el lado izquierdo se inicia desde el triángulo más grande a la más pequeña, mientras que la mano derecha hace lo contrario. Es evidente que ambas sumatorias son los mismos.

Answer 4

La idea de que mi respuesta es para descifrar los tres sumatorias en el lado izquierdo o lado derecho en las desigualdades. Entonces, yo uso el no codificado identidad para volver a escribir el otro lado de manera diferente. WLOG, voy a empezar en el lado derecho.
RHS = $\underbrace{\sum \limits_{\color{darkorange}{j}=1}^{n}}_{1 \leq \color{darkorange}{j} \leq n} \underbrace{\sum \limits_{\color{darkorange}{k}=1}^{j}}_{1 \leq \color{darkorange}{k} \leq j} \underbrace{\sum \limits_{\color{darkorange}{i}=1}^{k}}_{1 \leq \color{darkorange}{i} \leq k} 1 $

$\Longrightarrow 1 \leq j \leq n \, \& \, 1 \leq \color{limegreen}{k \leq j} \, \& \, 1 \leq \color{red}{i \leq k} $
$\Longrightarrow 1 \leq i \color{red}{\leq} k \color{limegreen}{\leq} j \leq n \tag{*} $

La clave es sólo para reescribir el combinado de la desigualdad anterior en tres de las desigualdades. Para obtener diferentes sumatoria de los límites, debemos asegurarnos de que al menos una de las nuevas desigualdades deben ser diferentes de los que están en (*).

1. Por lo tanto, debo corregir cualquiera de las $i$ o $k$ primera. WLOG, puedo elegir $k$: $1 \leq k \leq n. \tag{**}$
2. Después de la fijación de $k$, tengo que arreglar bien $i$ o $j$. WLOG, elegir $j$: $ k \color{limegreen}{\leq} j \leq n$
3. Después de la fijación de $j$ y $k$, $i$ queda fijo: $1 \leq i \color{red}{\leq} k$.

El de arriba da $\sum \limits_{k=1}^{n} \sum \limits_{j=k}^{n}\ \sum \limits_{1=i}^{k} 1$, NO del lado izquierdo, pero otra manera de volver a escribir la suma de los límites.

1. Para obtener la LHS, me doy cuenta de que yo necesitaba para arreglar $i$ primero en (**): $1 \leq i \leq n.$
2. Después de la fijación de $i$, tengo que arreglar bien $j$ o $k$. WLOG, elegir $j$: $ i \color{limegreen}{\leq} j \leq n$
3. Después de la fijación de $i$ y $j$, $k$ queda fijo: $i \color{red}{\leq} k \color{limegreen}{\leq} j$.

Los pasos #4-6 rendimiento de la LHS = $\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1$.