Cómo demostrar una estimación asintótica para $n \choose k$ donde $k = \mathcal{o}(n^{2/3})$ ?

Question

Sea $k = k(n)$ tal que $k \rightarrow \infty$ como $n \rightarrow \infty$ pero $k = \mathcal{o}(n^{2/3})$ . Utiliza la fórmula de Stirling $$n! = (1+\mathcal{o}(1))\sqrt{2\pi n} \biggl(\frac{n}{e}\biggr)^n$$ y la expansión de Taylor de $\ln(1+x)$ para demostrar que

$${n\choose k} = (1+\mathcal{o}(1))\frac{1}{\sqrt{2\pi n}} \biggl(\frac{n}{k}\biggr)^k \begin{cases} \exp(k) \quad \text{ for } k = \mathcal{o}(n^{1/2}) \\ \exp \biggl(k-\frac{k^2}{2n}\biggr) \quad \text{ for } k = \Omega(n^{1/2})\end{cases} .$$

Entiendo que por definición tenemos

$${n\choose k} = \frac{n!}{k! (n-k)!},$$

pero supongo que no podemos simplemente utilizar la fórmula de Stirling en $n!$ , $k!$ y $(n-k)!$ al mismo tiempo, así que no veo cómo proceder. ¿Podría darme una pista?

Answer 1

Supongo que no podemos simplemente utilizar la fórmula de Stirling en n!, k! y (nk)! al mismo tiempo, así que no veo cómo proceder.

¿Por qué no? Podemos reformular la fórmula de Stirling de la siguiente manera:

Existe una función $\psi:(-1,\infty)\to\Bbb R$ (o $\Bbb N_0\to\Bbb R$ si no quieres preocuparte por la función Gamma) tal que: $$x!=x^xe^{-x}\sqrt{2\pi x}\cdot(1+\psi(x))$$ Para todos $x>-1$ y: $$\lim_{x\to\infty}\psi(x)=0$$

Así, para cualquier $n\in\Bbb N_0$ y enteros $0\le k=k(n)\le n$ que tenemos: $$\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n^ne^{-n}\sqrt{2\pi n}(1+\psi(n))}{k(n)^{k(n)}e^{-k(n)}\sqrt{2\pi k(n)}\cdot(1+\psi(k(n))+(n-k(n))^{n-k(n)}e^{k(n)-n}\sqrt{2\pi(n-k(n))}\cdot(1+\psi(n-k(n))}$$

Desde $k\in o(n^{2/3})$ En particular, en $o(n)$ así que $k(n)\ll n$ para todo lo suficientemente grande $n$ en cuyo caso la expresión anterior es válida. Dado que estás derivando una asintótica, no te importa el pequeño $n$ así que puede darlo por hecho.

Podemos limpiar esto buceando por el factor más a la derecha del denominador: $$\binom{n}{k}=\frac{\left(\frac{n}{n-k}\right)^{n+1/2}(n-k)^{k}e^{-k}\cdot\frac{1+\psi(n)}{1+\psi(n-k)}}{1+\left(\frac{k}{n-k}\right)^{k+1/2}(n-k)^{-n}e^{n-2k}\cdot\frac{1+\psi(k)}{1+\psi(n-k)}}$$

Y podemos seguir la pista, tomando logaritmos. El logaritmo del numerador es: $$-\left(n-k+\frac{1}{2}\right)\log\left(1-\frac{k}{n}\right)+k\log(n)-k+\log\left(\frac{1+\psi(n)}{1+\psi(n-k)}\right)$$ Tenga en cuenta que $n-k\to\infty$ como $n-k\sim n\to\infty$ . El logaritmo de la derecha tiende entonces a $\log(1)=0$ así que terminaré con $o(1)$ (He introducido una función "explícita $\psi$ sólo para subrayar que el uso de la notación asintótica es realmente riguroso). $-\log(1-k/n)=k/n+\Theta(k^2/n^2)=k/n+o(n^{-2/3})$ (válido, como $k/n\to0$ ). Obtenemos: $$\frac{k-k^2}{n}+\frac{1}{2}\varphi(n)+k\log(n)-k+o(1)$$ Utilizando $n-k\sim n$ de nuevo, donde $\varphi(n)\sim k^2/n$ .

¿Cómo se comporta el denominador? Debes comprobar que el denominador tiende a $1$ y utilizar $\log(1+\cdots)$ de nuevo. Probablemente será bastante tedioso, pero este enfoque debería darte la respuesta correcta si lo haces con cuidado (mira, podría haber ignorado $\varphi(n)$ y por escrito $\Theta(k^2/n)$ pero veo las características de la expresión objetivo $k^2/2n$ por lo que parece que se necesitan más detalles).

Answer 2

Se deduce del resultado principal de este documento que $$ \log ((n + a)!) = \left( {n + a + \frac{1}{2}} \right)\log n - n + \frac{1}{2}\log (2\pi ) + \frac{{6a^2 + 6a + 1}}{{12n}} + \mathcal{O}\!\left( {\frac{{\max (\left| a \right|^3 ,1)}}{{n^2 }}} \right) $$ proporcionado $n + a+1 \ge 0$ y $\left| a+1 \right| < \frac{3}{5}n$ donde la constante implícita no depende de $n$ o $a$ . Entonces $$ \log (n!) = \left( {n + \frac{1}{2}} \right)\log n - n + \frac{1}{2}\log (2\pi ) + o(1), $$ $$ \log (k!) = \left( {k + \frac{1}{2}} \right)\log k - k + \frac{1}{2}\log (2\pi ) + o(1), $$ $$ \log ((n - k)!) = \left( {n - k + \frac{1}{2}} \right)\log n - n + \frac{1}{2}\log (2\pi ) + \frac{k^2}{{2n}} + o(1), $$ como $n,k\to +\infty$ con $k=o(n^{2/3})$ . En consecuencia, $$ \log \binom{n}{k} = - \frac{1}{2}\log (2\pi k) + k\log \left( {\frac{n}{k}} \right) + k - \frac{k^2}{{2n}} + o(1) $$ o $$ \binom{n}{k} = \frac{1}{{\sqrt {2\pi k} }}\left( {\frac{n}{k}} \right)^k \exp\! \left( {k - \frac{k^2}{{2n}}} \right)(1 + o(1)), $$ como $n,k\to +\infty$ con $k=o(n^{2/3})$ . Obsérvese que el factor $\sqrt{2\pi k}$ y no $\sqrt{2\pi n}$ .

Answer 3

Esto no responde exactamente a la pregunta

Consideremos el caso en que $k=n^a$ con $0\lt a \lt 1$ $$\binom{n}{k}=\binom{n}{n^a}=\frac{\Gamma (n+1)}{\Gamma \left(n+1-n^a\right)\, \Gamma \left(n^a+1\right)}$$

Tomando logaritmos y utilizando tres veces la aproximación de Stirling, es sencillo obtener $$\log \Bigg[\binom{n}{n^a}\Bigg]=\big[1+(1-a)\log(n)\big]n^a-\frac a2 \log(n)-\frac{1}{2} \log (2 \pi )+O\left(\frac{1}{n^a}\right)$$