Combinatoria mostrando el $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$

Question

Estoy tratando de mostrar que $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$. He encontrado que el uso stirling aproximación, puedo conseguir: $$ \lim_{n\to \infty}{\frac{2n\elegir n}{4^n}}= \lim_{n\to \infty}{\frac{(2n)!}{n!^2*2^{2n}}}= \lim_{n\to \infty}{\frac{(\frac{2n}{e})^{2n}\sqrt{2\pi (2n)}}{((\frac{n}{e})^n\sqrt{2\pi n})^2*2^{2n}}} =\lim_{n\to \infty}{\frac{2\sqrt{\pi n}}{2\pi n}} =0 $$

Pero esto parece poco elegante donde debería haber una forma más elegante, combinatoria prueba. Hay una manera más fácil?

Answer 1

No es un enfoque combinatorio, pero una forma divertida de hacerlo es mostrando que $$\frac{\binom{2n}{n}}{4^n}=\frac{1}{2\pi}\int_0^{2\pi} \cos^{2n} x\; dx$$

Básicamente, la escritura $\cos x = \frac12\left(e^{ix}+e^{-ix}\right)$. Por lo $\cos^{2n} x$ tiene término constante $\binom{2n}{n}/4^n$.

Desde $\cos^{2n} x\to 0$ en casi todas las $x$, es bastante fácil mostrar que la integral anterior tiende a cero, como se $n\to\infty$.
En concreto, en los intervalos de $(\varepsilon,\pi-\varepsilon)\cup(\pi+\varepsilon,2\pi-\varepsilon)$, $\cos^{2n}x\to 0$ de manera uniforme.

Answer 2

Aquí no combinatoria argumento de que evita la aproximación de Stirling.

$$\begin{align*} p_n\triangleq\frac{\binom{2n}n}{4^n}&=\frac{(2n)!}{(2^nn!)^2}\\\\ &=\frac{(2n)!(2n-1)!!^2}{(2n)!^2}\\\\ &=\frac{(2n-1)!!^2}{(2n)!}\\\\ &=\prod_{k=1}^n\frac{2k-1}{2k}\\\\ &=\prod_{k=1}^n\left(1-\frac1{2k}\right)\;, \end{align*}$$

así

$$\ln p_n=\sum_{k=1}^n\left(-\sum_{m\ge 1}\frac1{m(2k)^m}\right)\le-\sum_{k=1}^n\frac1{2k}=-\frac12H_n\;,$$

donde $H_n$ $n$- ésimo número armónico. La serie armónica diverge, por lo $\lim_{n\to\infty}\ln p_n=-\infty$, y por lo tanto $\lim_{n\to\infty}p_n=0$.

Nota: El doble factorial $(2n-1)!!$ es el producto de los enteros positivos impares que no exceda $2n-1$:

$$(2n-1)!!=\prod_{k=1}^n(2k-1)=\frac{(2n)!}{2^nn!}\;.$$

Answer 3

Otra era es el uso de la generación de la función de la central de los coeficientes binomiales, que es $$\frac{1}{\sqrt{1-x}}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}x^{n}.$$ We will make use of the fact that $x_{n}=\binom{2n}{n}\frac{1}{4^{n}}$ is a monotically decreasing sequence to make sure there are no oscillations. It is monotonic since $$x_{n+1}=\binom{2n}{n}\frac{1}{4^{n}}\frac{(2n+2)(2n+1)}{4\left(n+1\right)^{2}}=x_{n}\left(1-\frac{1}{2n+2}\right).$$ Taking the indefinite integral of both sides of the generating function, we have that for $|x|<1,$ $$2-2\sqrt{1-x}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}\frac{x^{n+1}}{n+1}.$$ Now, the left hand side converges as $x\rightarrow1$ from the left, and so, since the series has strictly positive coefficients, the right hand side must converge as well. This implies that $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}\frac{1}{n+1}$$ is a convergent series, and since the coefficients $\binom{2n}{n}\frac{1}{4^{n}}$ are monotonically decreasing, the divergence of the harmonic series implies that we must have $$\binom{2n}{n}\frac{1}{4^{n}}\rightarrow0.$$

Agrega Detalles: con Base en los comentarios, pensé que me iba a dar una precisión de la prueba de por qué la serie debe converger, sin recurrir a Littlewood del Tauberian teorema. La prueba sólo se requiere que los coeficientes de la alimentación de la serie, $a_n$, son no negativos. Vamos $a_n\geq0$, $s_m=\sum_{n=0}^m a_n$ ser las sumas parciales, y supongamos que $\sum_{n=0}^{\infty}a_{n}x^{n}\leq C$ todos los $x\in(0,1),$ para alguna constante positiva $C$. A continuación, para $x\in(0,1),$ $$s_{m}=\sum_{n=0}^{m}a_{n}\left(1-x^{n}\right)+\sum_{n=0}^{m}a_{n}x^{n}$$ $$\leq(1-x)\sum_{n=0}^{m}a_{n}\left(1+x+\cdots+x^{n-1}\right)+C$$

$$\leq(1-x)\sum_{n=0}^{m}na_{n}+C.$$ Taking $x$ sufficiently close to $1$, we can make $(1-x)\sum_{n=0}^{m}na_{n}\leq 1$, and so it follows that $s_{m}\leq C+1.$ This means that $s_m$ is monotonically increasing and bounded, its limit, $\sum_{n=0}^\infty a_n$ must converge. In particular, our series $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}(n+1)},$$ es convergente.

Answer 4

Aquí es lo que yo pienso "un enfoque combinatorio:" tenga en cuenta que $\binom{2n}{n}$ es el número de $n$ elemento de subconjuntos de a $2n$ elemento del conjunto. Considerar las cantidades $\binom{2n}{n+i},\,i=1,\ldots,k$ para algunos pequeños $k$ (en relación al $n$). Tenemos la relación de $\binom{2n}{n+1} = \frac{n}{n+1}\binom{2n}{n}$, y, en general, $\binom{2n}{n+k} = \frac{n-k+1}{n+k}\binom{2n}{n+k-1}$. Ahora para cualquier $k$, se puede elegir $n$ tan grande que $\frac{n-k+1}{n+k}$ al menos $1-\frac{1}{2k}$. Esto nos da la estimación de $\binom{2n}{n+k} \geq (1-\frac{1}{2k})\binom{2n}{n+k-1} \geq \cdots \geq (1-\frac{1}{2k})^k\binom{2n}{n} \geq \frac{1}{2}\binom{2n}{n}$. Por lo tanto, para cualquier $i\in\{1,\ldots,k\}$ e al $n$ es suficientemente grande, el número de $n+i$ elemento de subconjuntos de a $2n$ elemento del conjunto es, al menos,$\frac{1}{2}\binom{2n}{n}$. Por lo tanto, $\frac{k}{2}\binom{2n}{n} \leq 4^n$. Ahora, vamos a $k\rightarrow\infty$.

Answer 5

Hablando de la combinatoria de las pruebas,la $$ \sum_{k=0}^n\frac{\binom{2k}{k}}{2^{2k}}\frac{\binom{2(n-k)}{n-k}}{2^{2(n-k)}}=1. $$ El paso clave de una combinatoria prueba es que $p_k=\binom{2k}k2^{-2k}$ es la probabilidad de que la ruta de acceso aleatorio con $2k$ $(1,1)$ $(1,-1)$ no toque el $x$-eje después del inicio. Así que ahora vemos que la secuencia de la $p_k$ es monótona. Pero entonces la identidad de la primera, obviamente, implica $p_k\to0$ (si $\forall k\;p_k\gt\epsilon$, $1=\sum p_kp_{N-k}\gt N\epsilon\gt1$)