Más pequeña constante en exponente hasta ese límite de la suma es $0$

Question

Estoy tratando de trabajar el menor % constante $c>0$así % $ $$\lim_{n \to \infty} \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}} =0 .$

Si $c =3$ puedo ver que ciertamente no y si $c=2$ parece no hacerlo. ¿Cómo puede trabajar hacia fuera la constante exactamente?

Mi conjetura actual de un crudo uso de aproximación de Stirling es que $c> 6/e$ es necesario y suficiente.

Answer 1

Primero vamos a dar el doble de la suma de un nombre:

$$S_n = \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}}.$$

Ahora mirando el coeficiente binomial ${n-a \choose b}$ vemos que los términos con $b > n - a$ no juegan ningún papel. Así que también podría haber tomado la suma de$b = 0$$n - a$:

$$S_n = \sum_{a=1}^n \sum_{b=0}^{n-a} {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}}.$$

A continuación, podemos ver más de la estructura si el cambio de los índices de la doble sumatoria de la suma de más de $a,b$ a sumar más de $k = a+b$$a$. Desde $k$ pistas de $1$ $n$ $a$pistas de $1$ $k$a continuación, obtener

$$S_n = \sum_{k=1}^n \sum_{a=1}^k {n \choose a} {n-a \choose k-a} \left({k \choose a} 2^{-k}\right)^{c n/\ln{n}}.$$

Podemos simplificar aún más la inicial de dos binomios, señalando que, a $\binom{n}{a} \binom{n-a}{k-a} = \frac{n!}{a!(k-a)!(n-k)!} = \binom{n}{k} \binom{k}{a}$:

$$S_n = \sum_{k=1}^n {n \choose k} \sum_{a=1}^k {k \choose a} \left[{k \choose a} 2^{-k}\right]^{c n/\ln{n}}.$$

Considerando el término dentro de los corchetes, podemos obtener una cota superior de a $S_n$ reemplazando $a$$k/2$, y el uso de $\binom{k}{k/2} \sim 2^k \cdot \sqrt{2 / (\pi k)}$ como sigue:

$$\begin{align} S_n &\leq \sum_{k=1}^n {n \choose k} \sum_{a=1}^k {k \choose a} \left[\max_A {k \choose A} 2^{-k}\right]^{c n/\ln{n}} \\ &= \sum_{k=1}^n {n \choose k} \left[{k \choose k/2} 2^{-k}\right]^{c n/\ln{n}} \sum_{a=1}^k {k \choose a} \\ &\sim \sum_{k=1}^n {n \choose k} 2^k \left[\sqrt{\frac{2}{\pi k}}\right]^{c n/\ln{n}} \\ &= \sum_{k=1}^n {n \choose k} 2^k \exp\left(\frac{c n \ln(\frac{2}{\pi k})}{2 \ln n}\right) \\ &= \exp\left(\frac{c n \ln(2/\pi)}{2 \ln n}\right) \sum_{k=1}^n {n \choose k} 2^k \exp\left(- \frac{c n \ln k}{2 \ln n}\right) = T_n \\ &\left[= \exp\left(\frac{c n \ln(2/\pi)}{2 \ln n}\right) \sum_{k=1}^n {n \choose k} \exp\left(k \ln 2 - \frac{c n \ln k}{2 \ln n}\right) \right] \end{align}$$

Nota: en la última expresión que los términos que van a dominar la suma son los términos con $k \gg 0$; a continuación, tanto el término exponencial y los coeficientes binomiales aumento. Por otro lado, cuando se $k > n/2$ se vuelve demasiado grande, entonces en algún punto de los términos comienzan a disminuir de nuevo. Pero es claro que la suma está dominado por los términos con $k = O(n)$, y no en los términos con $k = o(n)$. Así que si vamos a reemplazar el $\ln k$ $\ln O(n)$ (pero no el$2^k$$2^{O(n)}$), se puede obtener una estimación de la cota superior de a $T_n$ como:

$$\begin{align} S_n \leq T_n &\approx \exp\left(\frac{c n \ln(2/\pi)}{2 \ln n}\right) \sum_{k=1}^n {n \choose k} 2^k \exp\left(- \frac{c n \ln O(n)}{2 \ln n}\right) \\ &\approx \exp\left(\frac{c n \ln(2/\pi)}{2 \ln n} - \frac{c n \ln O(n)}{2 \ln n}\right) \sum_{k=0}^n {n \choose k} 2^k \\ &\stackrel{(a)}{=} \exp\left(-\frac{c n}{2} + O\left(\frac{n}{\ln n}\right)\right) 3^n \\ &= \exp\left(\left(\ln(3)-\frac{c}{2}\right) n + O\left(\frac{n}{\ln n}\right)\right) \\ \end{align}.$$

Tenga en cuenta que en (a), he utilizado el hecho de que si $k = c_1 n$$0 < c_1 < 1$,$\ln k = \ln c_1 n = \ln c_1 + \ln n = \ln n + O(1)$, lo que significa que este plazo adicional desaparece en el orden en el plazo $O(n / \ln n)$. Por último, queremos que $S_n \leq T_n = o(1)$, lo que significa que $(\ln 3 - \frac{c}{2}) n = o(1)$, o en términos de $c$: $$c > \ln 9 \approx 2.19722.$$ Desde $S_n \leq T_n$ $T_n$ va a cero para $c > \ln 9$, esto muestra que para $S_n = o(1)$ basta con retirar $c > \ln 9$. Si $T_n$ es asintóticamente apretado entonces esta obligado también es necesario.

---

Para comprobar el resultado anterior, el gráfico siguiente muestra los valores numéricos para$S_n$$\color{red}{c = 2.19}$$\color{blue}{c = 2.20}$. Para$c = 2.19$, de hecho parece que $S_n \not\to 0$ grandes $n$, mientras que para $c = 2.20$ parece que la curva tiende a $0$$n \to \infty$. Esto no demuestra nada, pero ya que la curva de color rojo va al final parece muy probable que el punto de inflexión está por encima de $2.19$, y dado que la curva azul se parece a "acelerar" hacia la $0$$n \approx 200$, el punto de inflexión es probablemente por debajo del $2.20$.