Necesita un * trivial * prueba de un resultado combinatorio "obvio"

Question

Sólo me he presentado Enflo del teorema sobre la existencia de un espacio de Banach sin una aproximación de la propiedad en mi Análisis Funcional de la clase. El argumento es no trivial, de por sí, pero en el fin de enfatizar la realmente interesante pasos, me gustaría cerrar todos los "obvio" lemmata de la manera más eficiente.

He limpiado hasta el final un poco (si alguien está interesado, el derecho de elección de $k_m$$t_m$$t_{m+1}\in [t_1t_2\dots t_m,4t_1t_2\dots t_m]$$k_m=t_1t_2\dots t_{m-1}t_{m+1}$, lo que garantiza que todos interesantes coeficientes son enteros, entonces podemos hacer un ajuste perfecto sin ningún sucio de la cola de los límites y la estimación correspondiente; también es más fácil de usar sólo al azar las particiones horizontales en lugar de smart número de la teoría de las definiciones). Sin embargo, algunos desagradables piezas restantes.

El que me irrita más, es la siguiente:

Considerar todos los $n-1$-elemento subconjuntos $I$$\{1,2,\dots,2n\}$$m\in[1,2n-1]$. Deje $N_o$ $N_e$ ser los números de $I$'s de haber extraño e incluso el número de elementos en $\{1,\dots,m\}$ respectivamente. Entonces $$ |N_o-N_e|\le c_n(N_o+N_e)=c_n{2n\elegir n-1} $$ con algunos $c_n$ dependiendo $n$ (por lo que debe servir a todos los $m$ simultáneamente) tal que $\sum_n \frac{c_n}n<+\infty$.

La fuerte obligado es, por supuesto, $c_n=\frac 1n$ y Enflo obtiene considerando $m=1,2$ por separado y utilizando un trigonométricas representación integral y Titular de la desigualdad de otro $m$, en el que he perdido unos 35 minutos de la hora de clase, pero esto debe ser sólo una línea (OK, tal vez, tres) presentable en menos de 10 minutos (preferiblemente en menores de 5 años). Tenga en cuenta que no me importa sharp $c_n$ mientras que el de la serie anterior converge y estará encantado de comercio de su tamaño para cualquier simplificación en la prueba.

Así podemos hacer que este "obvio" hecho formalmente obvio?

Yo estoy pidiendo aquí en lugar de en MO porque es una educación pregunta en lugar de una investigación de uno :-)

Answer 1

Usted solicita una prueba en tres líneas, y muy bien la prueba de realidad se compone de tres operaciones :) te voy a romper la prueba a lo largo de estos cálculos. Sin embargo, en aras de la claridad, voy a añadir algunas líneas adicionales para explicar qué son las fórmulas de la media.

Primero algunas definiciones:

• $[n]:=\{1,\dots,n\}$ por entero positivo $n$.
• Para cualquier conjunto a $A$, definir:
  • La paridad $P(A):=|A|\mod 2$, considerado como un entero, 0 o 1.
  • La firma de $S(A) = (-1)^{P(A)}$
  • "Es este conjunto aún?" función de $E(A):=1-P(A)$. (P arriba es el "es este conjunto impar?" de la función).
• Para cualquier polinomio $p(x)$, definir $C_k\{p(x)\}$ a ser el coeficiente de $x^k$.

Línea 1:

$$N_e = \sum_{\substack{I\subset [2n] \\ |I|=n-1}} E(I\cap [m]) = \frac{1}{\binom{2n}{m}} \sum_{\substack{M\subset [2n] \\ |M|=m}} \sum_{\substack{I\subset [2n] \\ |I|=n-1}} E(I\cap M) = \frac{1}{\binom{2n}{m}} \sum_{\substack{I\subset [2n] \\ |I|=n-1}} \sum_{\substack{M\subset [2n] \\ |M|=m}} E(I\cap M) = \frac{\binom{2n}{n-1}}{\binom{2n}{m}} \sum_{\substack{M\subset [2n] \\ |M|=m}} E([n-1]\cap M)$$

Explicación:

• En primer lugar, y más importante, mi navegador se rompe esta en dos líneas, pero con una lo suficientemente grande en la pizarra encaja en uno.
• La primera igualdad dice que $N_e$ es el número de $n-1$ subconjuntos de a$[2n]$, incluso con intersección con $[m]$.
• Por simetría, el número de $n-1$ subconjuntos de a$[2n]$, incluso con intersección con $[m]$ es el mismo si se sustituye $[m]$ con cualquier otro $m$ subconjunto de $[2n]$. La segunda desigualdad sumas $N_e$ $m$ subconjuntos de a $[2n]$ y se divide por el número de subconjuntos.
• La tercera igualdad se cambia el orden de la suma. Ahora el interior de la suma representa el número de $m$ subconjuntos de a$[2n]$, incluso con intersección con un determinado $n-1$ subconjunto.
• El interior de la suma no le importa que $n-1$ subconjunto que tiene, por lo que el exterior de la suma es una suma de algunas constante a lo largo de todas las $n-1$ subconjuntos de a $[2n]$. Hay $\binom{2n}{n-1}$ estos subconjuntos, y esto le da la última igualdad.
• Si se divide por $\binom{2n}{n-1}$, esta ecuación puede ser interpretado como la probabilístico declaración de que la posibilidad de un seleccionados aleatoriamente $n-1$ tener incluso intersección con un determinado $m$ es la misma que la probabilidad de que un random $m$ incluso ha intersección con un determinado$n-1$. De esta forma, la verdad de la declaración es bastante obvio.
• Por último, de forma análoga ecuaciones presionado para$N_o$$N_e-N_o$, en sustitución de $E$ $P$ o $S$, respectivamente. El uno con $N_e-N_o$ $S$ serán utilizados a continuación. Explícitamente, los estados $$N_e-N_o = \frac{\binom{2n}{n-1}}{\binom{2n}{m}}\sum_{\substack{M\subset [2n] \\ |M|=m}} S([n-1]\cap M)$$

Línea 2:

$$ \begin{eqnarray} \sum_{\substack{M\subset [2n] \\ |M|=m}} S([n-1]\cap M) & = & \sum_k (-1)^k \binom{n-1}{k} \binom{n+1}{m-k} \\ & = & C_m\{(1-x)^{n-1}(1+x)^{n+1}\} \\ & = & C_m\{(1-x^2)^{n-1}(1+x)^2\} \\ & = & C_m\{(1-x^2)^{n-1}(1+2x+x^2)\} \\ & = & (C_m + 2C_{m-1} + C_{m-2})\{(1-x^2)^{n-1}\} \\ & = & \begin{cases} (-1)^{m/2} \binom{n-1}{m/2} - (-1)^{m/2}\binom{n-1}{m/2-1} & \quad \text{m even} \\ (-1)^{(m-1)/2} 2\binom{n-1}{(m-1)/2} & \quad \text{m odd}\end{casos} \end{eqnarray} $$

Explicación:

• Se me rompió la ecuación de arriba deliberadamente este tiempo, y no tengo ningún reparo. Si usted tiene una larga pizarra yada yada...
• La primera igualdad se rompe la suma de $m$ define por el número de elementos de a $k$ en la intersección de las $m$$[n-1]$. Para cada una de las $k$, $\binom{n-1}{k}$ maneras de elegir los elementos de la intersección y $\binom{n+1}{k}$ formas de elegir el resto de $m-k$ elementos de la $m$. Cada uno de estos lleva un peso $(-1)^k$ en la suma.
• La suma de $k$ puede ser expresada como un coeficiente $x^m$ en algunos polinomio producto, por el teorema del binomio, por lo tanto la siguiente igualdad.
• El siguiente par de igualdades reorganizar el polinomio producto.
• A continuación, tenga en cuenta que $C_m\{x p(x)\} = C_{m-1}\{p(x)\}$, y algunas propiedades similares a la de los coeficientes polinomiales.
• Por último, re-expandir $(1-x^2)^{n-1}$ a través de teorema del binomio y de identificar los coeficientes $m$, $m-1$, y $m-2$.

Esto le da una expresión para $$\frac{N_e-N_o}{\binom{2n}{n-1}} = \frac{1}{\binom{2n}{m}}\begin{cases} (-1)^{m/2} \binom{n-1}{m/2} - (-1)^{m/2}\binom{n-1}{m/2-1} & \quad \text{m even} \\ (-1)^{(m-1)/2} \binom{n-1}{(m-1)/2} & \quad \text{m odd}\end{cases}$$ Todo lo que queda es conveniente poner un límite en este, que es el contenido de la última línea.

Línea 3:

Supongamos por ahora que $m\leq n$. Deje $h(x):= -x\ln(x)-(1-x)\ln(1-x)$ ser la función de la entropía. Vamos a utilizar la estimación $$\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}$$ (enlace a la referencia) para obtener el siguiente enlazado:

$$\begin{eqnarray} \left|\frac{N_e-N_o}{\binom{2n}{n-1}}\right| & \leq & \frac{1}{\binom{2n}{m}}\begin{cases} \binom{n-1}{m/2} + \binom{n-1}{m/2-1} & \quad \text{m even} \\ \binom{n-1}{(m-1)/2} & \quad \text{m odd}\end{casos} \\ & \leq & \frac{1}{\binom{2n}{m}}\begin{cases} \binom{n}{m/2} & \quad \text{m even} \\ \binom{n}{(m-1)/2} & \quad \text{m odd}\end{casos} \\ & \leq & \begin{cases} \binom{n}{m/2}/\binom{2n}{m} & \quad \text{m even} \\ \binom{n}{(m-1)/2}/\binom{2n}{m-1} & \quad \text{m odd}\end{casos} \\ & \leq & \max_{k}\left\{\frac{\binom{n}{k}}{\binom{2n}{2k}}\right\} \\ & \leq & \max_k \left\{\frac{ \sqrt{\frac{n}{2\pi k (n-k)}} e^{n h(k/n)} }{ \sqrt{\frac{2n}{16k(2n-2k)}} e^{2n h(k/n)} } \right\} \\ & \leq & \max_k \left\{ \sqrt{\frac{8}{\pi}} e^{-n h(k/n)} \right\} \\ & \leq & \left\{ \sqrt{\frac{8}{\pi}} e^{-n h(1/n)} \right\} \\ & = & \sqrt{\frac{8}{\pi}} e^{-n \left(\frac{1}{n}\ln(n)-\frac{n-1}{n}\ln\left(\frac{n-1}{n}\right)\right)} \\ & \leq & \sqrt{\frac{8}{\pi}} \frac{1}{n} \\ \end{eqnarray} $$

Explicación:

• Primera desigualdad lleva a una norma de ambos lados de la ecuación de la línea 2, utilizando el triángulo de la desigualdad de la $m$ incluso el caso.
• Para la segunda desigualdad, para $m$ incluso sólo la suma de los dos coeficientes binomiales. Para $m$ impar, tenga en cuenta que por la misma fórmula de la suma de $\binom{n-1}{(m-1)/2}\leq \binom{n}{(m\pm 1)/2}$. Elegimos el signo menos debido a que de el siguiente paso, y ya que estamos suponiendo que inicialmente $m\leq n$.
• El siguiente paso sólo utiliza el hecho de que $\binom{2n}{m}\geq \binom{2n}{m-1}$$m\leq n$. Este es el único punto que el uso de esta hipótesis, y si $m\geq n$ usaremos $\binom{2n}{m}\geq\binom{2n}{m+1}$ en lugar de eso, también cambia el signo menos a un signo más en la parte anterior de la desigualdad. El resto del argumento se pasa a través de la misma, independientemente de si $m\geq n$ o $m\leq n$.
• La siguiente desigualdad elimina la $m$ dependencia mirando el máximo de la expresión anterior (ver nota abajo en el rango de $k$).
• A continuación, aplique los límites de los coeficientes binomiales (límite superior para el numerador, el límite inferior para el denominador).
• Simplificar.
• La entropía de la función $h$ es positivo, simétrico con respecto al $\frac{1}{2}$, y la monótona creciente en $[0,1/2]$, de ahí su min es el más pequeño permitido $k$, lo que nos puede llevar a ser $1$ (ver nota abajo en el rango de $k$).
• Simplificar. A continuación, tenga en cuenta que $e^{n \frac{n-1}{n} \ln\left(\frac{n-1}{n}\right)}<1$.

Nota sobre el rango de $k$: para que el mínimo de$h(k/n)$$k=1$, tenemos que el rango de $k$ a de$1$$n-1$. Desafortunadamente, esto significa que tenemos que excluir la $m=1$ $m=2n-1$ de los casos, ya que puede conducir a $k=0$ o $k=n$. Estos casos son fáciles de tratar, aunque, como en este caso $(N_e-N_o)/\binom{2n}{n-1}=1/n$.

En total, este le da la enlazado $c_n\leq \sqrt{\frac{8}{\pi}} \frac{1}{n}$.

---

Algunos comentarios:

• La estimación en la línea 3, probablemente podría ser mejorado. Una vez que tenga la forma cerrada de la solución, probablemente hay un montón de maneras de hacer las estimaciones. Yo no pretendo que la presentada aquí es óptima.
• El obligado en c_n se puede mejorar considerablemente si se excluye a $m=1,2n-1$.

Answer 2

Sólo una observación sobre la construcción de Yly la respuesta que me sugirieron poner como respuesta. La línea 3 se puede reemplazar con varios de los más elementales líneas.

En primer lugar observamos que la línea 2 queremos mostrar

$2{{n-1}\choose{(m-1)/2}}/{{2n}\choose{m}} \leq 1/n $ m impar.

$({{n-1}\choose{m/2}} - {{n-1}\choose{m/2 -1}})/{{2n}\choose{m}} \leq {{n}\choose{m/2}}/{{2n}\choose{m}}\leq 1/n$ m aun.

Ciertamente, estos son verdaderos para m=1, 2, y por simetría sólo tenemos que mostrarles a m=n. Ahora nos muestran ambas expresiones son la disminución en m hasta n. Primero el extraño caso, la sustitución de $m=2k+1$ hemos

$2{{n-1}\choose{k+1}}/{{2n}\choose{2k+3}} = \frac{2k+3}{2n-2k-1}*2{{n-1}\choose{k}}/{{2n}\choose{2k+1}}$

Mientras que para el caso de sustitución de $m=2k$ hemos

${{n}\choose{k+1}}/{{2n}\choose{2k+2}} = \frac{2k+1}{2n-2k-1}*{{n}\choose{k}}/{{2n}\choose{2k}}$

Answer 3

Actualización: Esta prueba no funciona como es, desde el $c_n$ deben ser independientes de $m$. Tal vez puede ser masajeado en la búsqueda de un $c_n$, que no depende de $m$, así que voy a dejar aquí.

---

Bueno, una super-sin inspiración prueba sería escribir $$ N_e-N_o=\sum_{k}{(-1)^k\binom{m}{k}\binom{2n-m}{n-1-k}}, $$ factor $\dfrac{(2n-m)!}{(n-1)!(n+1)!}$ así como para borrar los denominadores y los factores comunes en el numerador, y muestran que el $n^m$ términos en el resto de factor de cancelar porque $$ \sum_{k}{(-1)^k\binom{m}{k}=0}. $$ Eso significa que el resto de los factor es un polinomio de grado en la mayoría de las $m-1$, lo $c_n=O\left(\frac{1}{n}\right)$.