Encontrar un límite difícil

Question

¿Cómo se puede demostrar $\lim_{n \rightarrow \infty} n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}} = 1$? Sé que $\sum_{i=1}^{n}\frac{i (n!)}{(n-i)!n^{i}} = n$ pero no puedo ver cómo llegar de uno a otro.

Answer 1

Deje $X$ ser una discreta variable aleatoria que sigue Naor de distribución. Entonces su función de masa de probabilidad es: $$ \mathbb{P}\left(X=m\right) = \frac{m}{n^m} \frac{(n-1)!}{(n-m)!} [ 1 \leqslant m \leqslant n ] $$ La normalización de la condición conlleva $\sum_{m=1}^n \frac{m (n!)}{(n-m)! n^m} = n$. El Naor de distribución también está estrechamente relacionado con la distribución del número aleatorio uniforme de las muestras con reemplazo de de $n$ distintos elementos hasta la primera repetición (por ejemplo, ver aquí).

Reescribir el límite como $$ \lim_{n \rightarrow \infty} n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}} = \lim_{n \rightarrow \infty} \sum_{i=1}^{n}\frac{i(n-1)!}{(n-i)!(n+1)^{i}} $$

La suma en cuestión puede ser reformulado expectativa: $$ \sum_{m=1}^{n}\frac{m (n-1)!}{(n-m)!(n+1)^{m}} = \mathbb{E}\left( \left(\frac{n}{n+1}\right)^X \right) = \mathbb{E}\left( \left(1-\frac{1}{n+1}\right)^X \right) \geqslant \left(1-\frac{1}{n+1}\right)^{\mathbb{E}(X)} $$ donde la última desigualdad sigue por la desigualdad de Jensen. Por lo tanto tenemos: $$ 1 > \mathbb{E}\left( \left(1-\frac{1}{n+1}\right)^X \right) \geqslant \left(1-\frac{1}{n+1}\right)^{\mathbb{E}(X)} $$ Las reivindicaciones sigue ahora debemos establecer que $\mathbb{E}(X)$ crece más lento de lo $n$, es decir,$\mathbb{E}\left(X\right) \sim \mathcal{o}(n)$. La media se puede encontrar en forma cerrada en términos de incompleta $\Gamma$la función de: $$ \mathbb{E}\left(X\right) = -1 + \left(\frac{\mathrm{e}}{n}\right)^n \Gamma\left(n+1, n\right) $$ A partir de aquí tomamos prestado el resultado de la gran $n$ asymptotics de la $\Gamma(n+1,n)$: $$ \mathbb{E}\left(X\right) = \sqrt{\frac{\pi}{2} \cdot n} - \frac{1}{3} + \mathcal{s}(1) $$ Ahora, por el teorema del encaje de la gran $n$ límite de interés de la siguiente manera.

Answer 2

Usando lo que Sasha escribió en los comentarios, podemos evaluar la suma de la siguiente manera: $$\begin{eqnarray} \sum_{i=1}^{n-1} \frac{i}{n^i} \frac{(n-2)!}{(n-1-i)!} &\stackrel{i=n-1-k}{=}& \frac{(n-2)!}{n^{n-1}} \sum_{k=0}^{n-2} \left(n-1-k\right) \frac{n^k}{k!} = \frac{(n-2)!}{n^{n-1}} \sum_{k=0}^{n-1} \left(n-1-k\right) \frac{n^k}{k!} \\ &=& \frac{(n-1)!}{n^{n-1}} \sum_{k=0}^{n-1} \frac{n^k}{k!} - \frac{(n-2)!}{n^{n-2}} \sum_{k=1}^{n-1} \frac{n^{k-1}}{(k-1)!} \\ &=& \frac{(n-1)!}{n^{n-1}} \sum_{k=0}^{n-1} \frac{n^k}{k!} - \frac{(n-2)!}{n^{n-2}} \sum_{k=0}^{n-2} \frac{n^{k}}{k!} = \ldots \end{eqnarray} $$ El uso de, por $n\in \mathbb{N}$, $$ \frac{(n-1)!}{x^{n-1}} \sum_{k=0}^{n-1} \frac{x^k}{k!} = \mathrm{e}^x^{1-n} \Gamma(n,x) $$ y establecimiento $x=n$ seguimos $$ \ldots = \mathrm{e}^n n^{1-n} \Gamma(n,n) - \mathrm{e}^n n^{2-n} \Gamma(n-1,n) = \frac{n+1}{n-1} - \frac{1}{n-1} \frac{\mathrm{e}^n}{n^n} \Gamma(n+1,n) $$ donde la última igualdad se utiliza $n \Gamma(n,x) = \Gamma(n+1,x) - x^n \mathrm{e}^{-x}$ dos veces.

Ahora la reutilización de la gran $n$ comportamiento asintótico de $\frac{\mathrm{e}^n}{n^n} \Gamma(n+1,n) \sim \sqrt{\frac{\pi}{2} n }$ llegamos al límite.

Answer 3

Vamos a considerar una aplicación no uniforme de la partición donde$x=\frac{i^2}{n}$$\mathrm{d}x=\frac{2i}{n}$; luego tenemos a $i=\sqrt{nx}$.

Tenga en cuenta que $$ \frac{(n-2)!}{(n-1-i)!n^{i-1}} =\frac{n-2}{n}\frac{n-3}{n}\dots\frac{n-i}{n} $$ El uso, la Desigualdad de Bernoulli, obtenemos $$ \left(1-\frac en\right)^{\frac2i+\frac3i+\dots+\frac ii} \le\frac{n-2}{n}\frac{n-3}{n}\dots\frac{n-i}{n} \le\left(1-\frac1n\right)^{2+3+\dots+i}\\ \left(1-\frac en\right)^{(i+2)(i-1)/(2i)} \le\frac{(n-2)!}{(n-1-i)!n^{i-1}} \le\left(1-\frac1n\right)^{(i+2)(i-1)/2} $$ a continuación, utilizando el teorema del sándwich, conseguimos que los $\frac{(n-2)!}{(n-1-i)!n^{i-1}}\to e^{-x/2}$.

Sumando a $i\le\sqrt{\lambda n}$ es equivalente a $x\le\lambda$, y esto es equivalente a la suma de Riemann para $$ \begin{align} \lim_{n\to\infty}n\sum_{i=1}^{\sqrt{\lambda n}}\frac{i(n-2)!}{(n-1-i)!n^{i+1}} &=\lim_{n\to\infty}\sum_{i=1}^{\sqrt{\lambda n}}\frac{(n-2)!}{(n-1-i)!n^{i-1}}\frac in\\ &=\int_0^\lambda e^{-x/2}\,\frac{\mathrm{d}x}{2}\\ &=1-e^{-\lambda/2} \end{align} $$ Desde $\lambda$ fue arbitrario, tenemos que $$ \lim_{n\to\infty}n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}}=1 $$