Atascado tratando de demostrar una desigualdad

Question

He estado tratando de probar (la mitad izquierda de) la siguiente desigualdad:

$$ \underbrace{\sum_i \sum_j |x_i| \le \sum_i \sum_j |x_i + x_j|}_\textrm{?} \le 2 \sum_i \sum_j |x_i|$$

(Todos los $x_i$s son arbitrarias de reales y las sumas son más de $1, 2, \dots, n$)

La mitad derecha de la siguiente manera por la simple aplicación de la desigualdad de triángulo, pero la parte de la izquierda no es tan simple.

Traté de inducción, y yo podría reducir el problema anterior para probar la siguiente declaración:

$$ \sum_i |x_i + x_{n+1}| + \sum_{i=1}^{n+1} |x_i + x_{n+1}| \ge \sum_{i=1}^{n+1} |x_i| + n|x_{n+1}|$$ o, más sencillamente (en sustitución de $x_{n+1}$$y$), $$ 2\sum_i |x_i + y| \ge \sum_i |x_i| + (n-1)|y|$$

Sin embargo, no sé si los de arriba "reducción" es más simple que el problema original en sí mismo!

Puedo continuar con la anterior línea de pensamiento, o es que hay una manera más fácil de resolver este problema? Cualquier ayuda es muy apreciada. :)

Answer 1

Creo que algunos inteligentes trucos va a resolver el problema (por ejemplo, mediante la refundición de la misma en la forma de algún conocido de la desigualdad), pero lo que vino a mi mente fue una prueba inspirado por el método simplex. A pesar de que no parece inteligente, puede ser de algunos intereses a los lectores:

1. Tenga en cuenta que por la ampliación de la desigualdad, podemos suponer sin pérdida de generalidad, que el $|x_i|\le1$ todos los $i$.
2. Así que queremos demostrar la desigualdad para todos los $(x_1,\ldots,x_n)$ dentro del hipercubo $[-1,1]^n$.
3. Dividir el hipercubo $[-1,1]^n$ en pedazos por el hyperplanes $x_i=x_j$$x_i=0$. Por ejemplo, cuando se $n=2$, las cuatro "hyperplanes" (líneas rectas, en este caso) $x=y$, $x=-y$, $x=0$ y $y=0$ se divide el cuadrado de $[-1,1]^2$ en ocho piezas en una manera similar a la de la Union Jack.
4. En matemáticas, llamamos a cada una de estas piezas de un simplex.
5. Tenga en cuenta que dentro de cada simplex, cada una de las $x_i$ o $x_i+x_j$ no cambia de signo.
6. Por lo tanto, dentro de cada simplex, la función de $f(x_1,\ldots,x_n)=-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|$ es idéntica a $-\sum_i \sum_j s_ix_i + \sum_i \sum_j t_{ij}(x_i + x_j)$ para algunas constantes $s_i, t_{ij}=\pm1$.
7. En otras palabras, $f$ es una función lineal dentro de cada simplex.
8. En la programación lineal, es bien sabido que el extremo de una función lineal puede ser alcanzado en las esquinas de la cara. Usted puede imaginar que, cuando se mueve en un plano más cerca y más cerca de un simplex, toque el simplex en una esquina de la primera (o se toca el rostro, con las esquinas de la cara incluido).
9. Los rincones de nuestro simplices, sin embargo, son los puntos que $x_i\in\{-1,0,1\}$.
10. Así, sólo tenemos que demostrar la desigualdad de estos puntos de esquina.
11. Deje $a$ de la $x_i$s son iguales a 1, $b$ de ellos son iguales a $-1$ $n-a-b$ de ellos son iguales a cero. Entonces $$ \begin{align} &-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|\\ =&-n(a+b) + 2a^2+2b^2+2a(n-a-b)+2b(n-a-b)\\ =&2a^2+2b^2 - 2(a+b)^2 + n(a+b)\\ \ge&2a^2+2b^2 - 2(a+b)^2 + (a+b)^2\\ =&(a-b)^2\\ \ge&0. \end{align} $$
12. De ahí el resultado.

En el paso 11 de la anterior, la igualdad tiene iff $a-b=0$$a+b\in\{0,n\}$. En otras palabras, la igualdad tiene iff $a=b=0$ o $a=b=n/2$, es decir, iff todos los $x_i$s son cero, o al $n$ es incluso, exactamente la mitad de la $x_i$s (antes de la ampliación) son idénticas a las de algunos $x$ y la otra mitad son de $-x$s. Sin embargo, esta condición de igualdad se derivan de la utilización de los puntos de esquina. La anterior prueba no indica si la igualdad no puede sostener en otros casos.

Answer 2

Asumir un pedido de la $x_i$ tal que $x_1 \le x_2 \le \dots \le x_k < 0 \le x_{k+1} \le x_{k+2} \le \dots \le x_n$. Vamos a llamar a $T_1 = \sum_{i=1}^k |x_i|$, $T_2 = \sum_{i=k+1}^n |x_i|$, y $T=\sum_i |x_i|=T_1+T_2$, de modo que $T, T_1, T_2 \ge 0$.

Ya que sólo requieren de un límite inferior en la suma de $\sum_{i \neq j} |x_i + x_j|$, se considera sólo a $2\binom{k}{2} + 2\binom{n-k}{2}$ términos de la $2\binom{n}{2}$ total de términos que la suma contiene es decir, que sólo escoge los términos tanto en $x_i$ $x_j$ tienen el mismo signo. Esto resuelve la desigualdad en muchos casos. Para los otros casos, se incluye la cruz términos demasiado tarde.

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=1,j\neq i}^k |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n |x_i+x_j|\\ &= \sum_{i=1}^k \sum_{j=1,j\neq i}^k (|x_i|+|x_j|) + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n (|x_i|+|x_j|)\\ &= \sum_{i=1}^k ((k-1)|x_i|+T_1-|x_i|) + \sum_{i=k+1}^n ((n-k-1)|x_i|+T_2-|x_i|)\\ &= \sum_{i=1}^k ((k-2)|x_i|+T_1) + \sum_{i=k+1}^n ((n-k-2)|x_i|+T_2)\\ &= ((k-2)T_1+kT_1) + ((n-k-2)T_2+(n-k)T_2)\\ &= 2\{(k-1)T_1 + (n-k-1)T_2\}\\ \end{align*} $$

Ahora, la última expresión es una función de $T_1$$T_2$. Desde que requieren un límite inferior en términos de $T=T_1+T_2$, podemos obtener dos expresiones equivalentes en términos de $T_1$ $T$ o en términos de$T_2$$T$. Por lo tanto,

$$\sum_{i \neq j} |x_i + x_j| \ge 2(2k-n)T_1+2(n-k-1)T$$ $$\sum_{i \neq j} |x_i + x_j| \ge 2(n-2k)T_2+2(k-1)T$$

La adición de ambos, se obtiene:

$$2\sum_{i \neq j} |x_i + x_j| \ge 2\left\{(2k-n)T_1+(n-2k)T_2+(n-2)T\right\}$$ $$\implies \sum_{i \neq j} |x_i + x_j| \ge (2k-n)(T_1-T_2)+(n-2)T \ge (n-2)\sum_i |x_i|$$ $$ \text{whenever,} \; (2k-n)(T_1-T_2) \ge 0$$

Para los casos en que la desigualdad anterior no se cumpla, debemos considerar la cruz términos demasiado. El cómputo de la cruz términos solos:

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=1}^k |x_i+x_j|\\ &\ge 2\sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j|\\ &\ge 2\sum_{i=1}^k \sum_{j=k+1}^n \max\{|x_i|-|x_j|,|x_j|-|x_i|\}\\ &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\}\\ \end{align*} $$

Incluyendo la cruz términos junto con los términos y condiciones en el caso anterior, tenemos:

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\} + 2\{(k-1)T_1 + (n-k-1)T_2\}\\ &\ge 2 \max\{(n-1)T_1+(n-2k-1)T_2, (2k-n-1)T_1+(n-1)T_2\} \; (*)\\ \end{align*} $$

El $\max$ plazo que puede ir de dos maneras. Utilizando el primer término, se obtiene: $$ \sum_{i \neq j} |x_i + x_j| \ge 2 \{(n-1)T_1+(n-2k-1)T_2\} $$

Podemos volver a escribir la anterior en términos de $T,T_1$ o $T,T_2$ da dos desigualdades:

$$ \begin{align} \sum_{i \neq j} |x_i+x_j| &\ge (n-2k-1)T+2kT_1\\ \sum_{i \neq j} |x_i+x_j| &\ge (n-1)T-2kT_2 \end{align} $$

Sumando los dos anteriores desigualdades,

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge (2n-2k-2)T+2k(T_1-T_2)\\ &\ge (n-2)T+(n-2k)T+2k(T_1-T_2)\\ &\ge (n-2)T \quad \text{for the case} \quad (2k-n) \le 0, (T_1-T_2) \ge 0\\ \end{align*} $$

Del mismo modo, para el otro caso, cuando se $(2k-n) \ge 0, (T_1-T_2) \le 0$, utilizamos el otro $\max$ plazo de $(*)$ y siga los pasos anteriores de forma rutinaria para demostrar la desigualdad.

Q. E. D

Answer 3

Deje $p$ el número de $x_i\ge0$, $m$ ser el número de $x_i<0$, e $n=p+m$. $$ \pequeño\begin{array}{} &\sum_i\;\:\sum_j|x_i+x_j|\\ &=\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i+x_j| &+\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i+x_j| &+\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_i+x_j| &+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i+x_j|\\ &\ge\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i|+|x_j| &+\left|\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i|-|x_j|\right| &+\left|\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_j|-|x_i|\right| &+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i|+|x_j|\\ &=2p\sum_{x_i\ge0}|x_i| &+2\left|m\sum_{x_i\ge0}|x_i|-p\sum_{x_i<0}|x_i|\right| &&+2m\sum_{x_i<0}|x_i| \end{array} $$

Restando $\displaystyle\sum_i\;\:\sum_j|x_i|=n\sum_i\;|x_i|$ de la desigualdad por encima de los rendimientos $$ \pequeño\begin{align}{} &\sum_i\;\:\sum_j|x_i+x_j|-\sum_i\;\:\sum_j|x_i|\\ &\ge(p-m)\sum_{x_i\ge0}|x_i| +\left|2m\sum_{x_i\ge0}|x_i|-2p\sum_{x_i<0}|x_i|\right| +(m-p)\sum_{x_i<0}|x_i|\\ &=(p-m)\sum_{i}x_i +\left|(m-p)\sum_{i}|x_i|+n\sum_ix_i\right|\\ &\ge0\tag{1} \end{align} $$ En la última desigualdad, si $p-m$ $\sum\limits_ix_i$ tienen el mismo signo, podemos ignorar la cantidad en valores absolutos. Si $p-m$ $\sum\limits_ix_i$ tienen signos diferentes, entonces las cantidades en los valores absolutos tienen el mismo signo y $|m-p|\sum\limits_i|x_i|\ge(m-p)\sum\limits_ix_i$.

Por lo tanto, $(1)$ dice que $$ \sum_i\;\:\sum_j|x_i|\le\sum_i\;\:\sum_j|x_i+x_j| $$