Comportamiento asintótico de $\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k$

Question

Estoy buscando para ver que %#% $ #% en mi solicitud, $$\lim_{n \rightarrow \infty}\frac{1}{e^n}\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k = 0. $. He estado buscando por todo el lugar, pero parece que no puedo encontrar una expresión de forma cerrada o un buen límite superior para la suma.

La estimación obvia $c = (e+1)/2 \approx 1.85914\ldots$ $ no hará el truco, desde $$\sum_{k=1}^n \binom{n}{k} \left(c\frac{k}{n}\right)^k \leq \sum_{k=0}^n \binom{n}{k} \left(c\right)^k \leq \left(1+c\right)^n $.

¿Alguna idea?

Answer 1

Simple Aproximación de Bernoulli con la Inequalty

Usando la Desigualdad de Bernoulli, vemos que $$ e^{-k}\le\left(1-\frac{k}{n}\right)^{n-k}\le e^{-k(1-k/n)}\etiqueta{1} $$ Por lo tanto, $$ \begin{align} \lim_{n\to\infty}\frac1{e^n}\sum_{k=1}^n\binom{n}{k}\left(\frac{ck}{n}\right)^k &=\lim_{n\to\infty}\frac1{e^n}\sum_{k=0}^n\binom{n}{k}\left(\frac{c(n-k)}{n}\right)^{n-k}\\ &=\lim_{n\to\infty}\frac1{e^n}\sum_{k=0}^n\binom{n}{k}c^{n-k}\left(1-\frac{k}{n}\right)^{n-k}\\ &=\lim_{n\to\infty}\sum_{k=0}^n\binom{n}{k}\left(\frac ce\right)^{n-k}\left[\frac1{e^2},\frac1{e^{2-k/n}}\right]^k\tag{2} \end{align} $$ $(2)$ dice que el límite es el infinito si $c\gt e-\frac1e=2.3504023872876029138$.

El Teorema del Límite Central dice que como $n\to\infty$, la principal contribución a la $$ \sum_{k=0}^n\binom{n}{k}x^{n-k}y^k\etiqueta{3} $$ se produce dentro de una $O\left(n^{-\frac12+\epsilon}\right)$ barrio de $\frac kn=\frac{y}{x+y}$. Si queremos abreviar $\frac kn=\alpha$, tenemos que el límite es de $0$ si $c\lt e-\frac1{e^{1-\alpha}}$ donde el Teorema del Límite Central da $\frac1\alpha-1=ce^{1-\alpha}$. La solución para $\alpha$, obtenemos $$ \begin{align} \left(\frac1\alpha-1\right)e^{\alpha-1} &=e-e^{\alpha-1}\\ &\Downarrow\\ \alpha &=-\mathrm{W}\left(-e^{-2}\right)\\ &=0.15859433956303936215\tag{4} \end{align} $$ $(4)$ de los rendimientos que el límite es de $0$ si $c\lt2.287177717128371900838$.

Desde $\frac{e+1}2\lt2.287177717128371900838$, cuando se $c$ está cerca de a $\frac{e+1}{2}$, el límite es de $0$.

Este simple argumento no puede decir lo que sucede para $$ 2.287177717128371900838\lt c\lt2.3504023872876029138\etiqueta{5} $$

---

Más de Precisión con el Método de Laplace

Para más precisión, de Laplace, el Método puede ser adaptado para manejar la suma $$ e^{-n}\sum_{k=0}^n\binom{n}{k}\left(\frac{ck}{n}\right)^k\etiqueta{6} $$ En el Método de Laplace, la integral es $$ \sqrt{\frac{2\pi}{s(x\text{max})}}f(x\text{max})\etiqueta{7} $$ donde$s(x)=-\frac{\mathrm{d}^2}{\mathrm{d}x^2}\log(f(x))$$f'(x_\text{max})=0$.

---

La primera diferencia de $\log\binom{n}{k}$$\log\left(\frac{n-k}{k+1}\right)$. La derivada de $k\log\left(\frac{ck}{n}\right)$$1+\log\left(\frac{ck}{n}\right)$. Por lo tanto, vamos a aproximar la primera derivada del registro de la sumando por $$ \log\left(\frac{ce(n-k)}{n}\right)=\log(ce(1-\alpha))\etiqueta{8} $$ donde $\alpha=\frac kn$. Así, la máxima de que el integrando es cuando $$ ce(1-\alpha)=1\etiqueta{9} $$ El negativo de la derivada segunda del registro de la sumando al máximo, a continuación, $$ \frac1{n-k}=\frac1{n(1-\alpha)}=\frac{ce}{n}\etiqueta{10} $$ Calcular el valor del sumando al máximo el uso de la fórmula de Stirling: $$ \begin{align} &\frac1{\sqrt{2\pi n}}\sqrt{\frac{n^2}{k(n-k)}}\frac{n^n}{k^k(n-k)^{n-k}}\frac{c^kk^k}{n^ke^n}\tag{11}\\ &=\frac1{\sqrt{2\pi n\alpha(1-\alpha)}}\left(\frac{c^\alpha}{e(1-\alpha)^{1-\alpha}}\right)^n\tag{12}\\ &=\frac1{\sqrt{2\pi n\alpha(1-\alpha)}}\left(ce^{-\alpha}\right)^n\tag{13}\\ &=\frac{ce}{\sqrt{2\pi n(ce-1)}}\left(\frac cee^{\large\frac1{ce}}\right)^n\tag{14} \end{align} $$ El uso de $(7)$, $(10)$, y $(14)$, obtenemos la suma de $(6)$ a ser asintótica $$ \begin{align} \sqrt{\frac{ce}{ce-1}}\left(\frac cee^{\large\frac1{ce}}\right)^n\tag{15} \end{align} $$ Fórmula $(15)$ indica que el breakpoint en $c$ entre el límite de $0$ e se $\infty$ es al $\frac cee^{\large\frac1{ce}}=1$; es decir, $$ \begin{align} c &=-\frac1{e\mathrm{W}\left(-e^{-2}\right)}\\[6pt] &\doteq2.3196252917035202431\tag{16} \end{align} $$ Tenga en cuenta que el $c$ $(16)$ es casi en el medio de la gama dada en $(5)$. Al $c$ es igual al valor en $(16)$, obtenemos $$ \sqrt{\frac{ce}{ce-1}}=1.0901776779197391224\etiqueta{17} $$ El uso de Mathematica 8, calcular la suma de $(6)$ $c$ $(16)$ $n=100000$ rendimientos $1.090178422502261$; muy cerca de $(17)$.

---

Para $c=\frac{e+1}{2}$, la aproximación a $(15)$ dice que la suma es asintótica $$ 1.1165527750632721\times0.8335934600537050^n\etiqueta{18} $$ Para $n=500$, $(18)$ da $3.34987509422\times10^{-40}$, mientras que el real cálculo de los rendimientos de $3.35051202913\times10^{-40}$, un error de menos de $0.02\%$.

Answer 2

Para tener una idea de la asymptotics, trate de usar Stirling aproximación de los coeficientes binomiales:

$$\begin{align}\ln \left[{n \choose k} \left(\frac{c k}{n}\right)^k\right] &\sim \left[n \ln n - k \ln k - (n - k) \ln(n - k)\right] + \left[k \ln c + k \ln k - k \ln n\right] \\ &\sim (n-k) \ln\left(\frac{n}{n - k}\right) + k \ln c. \tag{1}\end{align}$$

Ahora, a ver donde la principal "peso" de la suma, es decir, para que los valores de $k$ los sumandos son los más grandes, sólo tomamos la derivada con respecto al $k$, es igual a $0$, y resolver para $k$:

$$1 + \ln \left(\frac{n-k}{n}\right) + \ln c = 0 \implies k = \left(1 - \frac{1}{ce}\right)n$$

Conectar este valor de $k$ a $(1)$, obtenemos que para este valor de $k$ el sumando se convierte en

$${n \choose k} \left(\frac{c k}{n}\right)^k \sim \exp\left(\left(\ln c + \frac{1}{e c}\right)n\right).$$

Así que para un gran $n$, todo el argumento de que el límite (incluyendo el término $e^n$) como las escalas de

$$\exp\left(\left(\ln c + \frac{1}{e c} - 1\right) n\right).$$

Rellenar $c = (e + 1)/2$ tenemos un exponente negativo garantizar la convergencia de la orden de $e^{-0.182009 n} = 2^{-0.26258\dots n}$. Podemos verificar estos resultados de forma numérica, por ejemplo, para $n = 500$ el valor exacto es$3.35051\ldots \cdot 10^{-40}$, mientras que la aproximación asintótica nos da $3.00019\ldots \cdot 10^{-40}$. El orden de magnitud es exactamente correcto, y sólo la constante es levemente por sobre $10\%$.

---

Si a usted le gustaría saber para qué valores de a $c$ consigue la convergencia, usted sólo tiene que encontrar la salida, cuando el exponente es negativo:

$$\ln c + \frac{1}{e c} - 1 < 0 \iff c(1 - \ln c) < \frac{1}{e}.$$

Sustituyendo $c = e \cdot d$, $1$ en el lado izquierdo desaparecer:

$$d \ln d > \frac{-1}{e^2}.$$

Esto no puede ser resuelto con funciones elementales, pero el uso de la función W de Lambert tenemos

$$d < e^{W(-1/e^2)} \implies c < e^{1 + W(-1/e^2)} = 2.31963\ldots.$$

Answer 3

Yo también estaba trabajando con la desigualdad

$$ \left(1 - \frac{k}{n}\right)^{n-k} \leq \exp \left( -k + \tfrac{k^{2}}{n} \right) = \exp\left\{ -n \cdot \tfrac{k}{n} \left( 1 - \tfrac{k}{n} \right) \right\}.$$

Ahora tenga en cuenta que $q(x) = x(1-x)$ satisface $q(1-x) = q(x)$$q(x) \geq \frac{1}{2}x $$[0, \frac{1}{2}]$. A continuación, obtenemos

$$ 0 \leq k \leq \tfrac{1}{2}n \quad \Longrightarrow \quad \exp\left\{ -n \cdot \tfrac{k}{n} \left( 1 - \tfrac{k}{n} \right) \right\} = e^{-nq(k/n)} \leq e^{-k/2}. \tag{*} $$

Para utilizar esta obligado, dividimos la suma en dos parte:

\begin{align*} S_{n} := e^{-n} \sum_{k=0}^{n} \binom{n}{k} \left( \frac{k}{n} \right)^{k} c^{k} &= e^{-n} \sum_{k=0}^{n} \binom{n}{k} \left( 1 - \frac{k}{n} \right)^{n-k} c^{n-k} \\ &\leq e^{-n} \sum_{k=0}^{n} \binom{n}{k} c^{n-k} e^{-nq(k/n)} \\ &\leq e^{-n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} c^{n-k} e^{-nq(k/n)} + e^{-n} \sum_{\frac{n}{2} \leq k \leq n} \binom{n}{k} c^{n-k} e^{-nq(k/n)} \\ &= (c/e)^{n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} c^{-k} e^{-nq(k/n)} + e^{-n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} c^{k} e^{-nq(k/n)}. \end{align*}

Aquí, en la última línea, se aplicó el cambio de índice de $k \mapsto n-k$. Entonces podemos usar $\text{(*)}$ y se obtiene el siguiente crudo obligado:

\begin{align*} S_{n} &\leq (c/e)^{n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} \left( \frac{1}{c\sqrt{e}} \right)^{k} + e^{-n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} \left( \frac{c}{\sqrt{e}} \right)^{k} \\ &\leq \left\{ \frac{c}{e} \left( 1 + \frac{1}{c\sqrt{e}} \right) \right\}^{n} + \left\{ \frac{1}{e} \left( 1 + \frac{c}{\sqrt{e}} \right) \right\}^{n}. \end{align*}

Ahora tenga en cuenta que $c > 0$ satisface la siguiente condición

$$ \frac{c}{e} \left( 1 + \frac{1}{c\sqrt{e}} \right) < 1 \quad \text{y} \quad \frac{1}{e} \left( 1 + \frac{c}{\sqrt{e}} \right) < 1 \quad \Longleftrightarrow \quad c < e - \frac{1}{\sqrt{e}} \simeq 2.111751169. $$

Desde su $c$ es de menos de $2$, la demanda de la siguiente manera.

---

Un poco en general, se puede introducir un parámetro de $\delta \in (0, 1)$. Entonces

\begin{align*} \begin{array}{cl} 0 \leq k \leq \delta n & \quad \Longrightarrow \quad \left( 1 - \tfrac{k}{n} \right)^{n-k} \leq e^{-(1-\delta)k}, \\ 0 \leq k \leq (1-\delta) n & \quad \Longrightarrow \quad \left( 1 - \tfrac{k}{n} \right)^{n-k} \leq e^{-\delta k} \end{array} \end{align*}

y nuestra estimación es refinado como

$$ S_{n} \leq \left( \frac{c}{e} + \frac{1}{e^{2-\delta}} \right)^{n} + \left( \frac{1}{e} + \frac{c}{e^{1+\delta}} \right)^{n}. $$

Para ambas ratios a ser menor que 1, debemos tener $c < \min\{ e - e^{\delta-1}. e^{\delta}(e - 1) \}$. La maximización de esta enlazado da

$$ e^{\delta} = \frac{1 + e^{-1}}{1 + e^{-3}}, $$

Por lo tanto

$$ c < \frac{e^{2} e^{2} - 1)}{e^{3} + 1} \quad \Longrightarrow \quad S_{n} \leq \left( \frac{c}{e} + \frac{1}{e^{2}-e+1} \right)^{n} + \left( \frac{1}{e} + \frac{e^{2}-e+1}{e^{3}} c \right)^{n} \xrightarrow[n\to\infty]{} 0. $$

Answer 4

Sabemos que $\dbinom{n}{k} \le \left(\dfrac{e\,n}{k}\right)^k$. Por lo tanto, $$\sum_{k=1}^n \binom{n}{k} \left(c\frac{k}{n}\right)^k \le \sum_{k=1}^n \left(\dfrac{e\,n}{k}\right)^k \left(c\frac{k}{n}\right)^k = \sum_{k=1}^n (e\,c)^k = \frac{(e\,c)^{n+1}-1}{e\,c-1}$ $

Answer 5

Para calcular la suma , considerar en primer lugar, incluso, $n$ y tenga en cuenta lo siguiente:

• $c = \frac{(1+e)}{2} \approx 1.85914\dots < e$, y por lo tanto, el último término de la suma de $k=n$ puede ser ignorado como $\binom{n}{n}\left(\frac{c}{e}\right)^n \rightarrow 0$$n \rightarrow \infty$.
• $\binom{n}{k} = \binom{n}{n-k}$, y por lo tanto, ambos términos se $\binom{n}{k}\left(c \frac{k}{n}\right)^k$ $\binom{n}{k}\left(c \frac{n-k}{n}\right)^{n-k}$ tienen el mismo coeficiente binomial en la suma.
• La idea es calcular la suma de dos términos por una función exponencial de la forma $c \mapsto e^{m k + b}$ donde $m$ $b$ solo depende de los $n$$c$.
• De hecho, el registro de la suma, la función de $k \mapsto \log\left( \left(c\frac{k}{n}\right)^k + \left(c\frac{n-k}{n}\right)^{n-k} \right)$, es estrictamente convexa en el intervalo de $\left[1,\frac{n}{2}\right]$ es superior delimitado por la función lineal $$ f(k) = \left(\frac{\log(4)}{n}-\log(2c)\right) k + n \log(c).$$
• Por lo tanto, $$\binom{n}{k}\left(c\frac{k}{n}\right)^k + \binom{n}{n-k}\left(c\frac{n-k}{n}\right)^{n-k} \leq \binom{n}{k} e^{f(k)}.$$

Podemos obligado por la suma \begin{eqnarray} \frac{1}{e^n} \sum_{k=1}^{ \frac{n}{2} } \binom{n}{k} e^{f(k)} & = & \frac{1}{e^n} \sum_{k=1}^{\frac{n}{2}} \binom{n}{k} 4^{\frac{k}{n}} c^n \left(\frac{1}{2c}\right)^k \\ & \leq & 4\frac{c^n \left(1+ \frac{1}{2c}\right)^n}{e^n} \\ & = & 4\left(\frac{\frac{1}{2} + c}{e}\right)^n \approx 4\left(\frac{2.35914}{e}\right)^n. \end{eqnarray} Desde $2.35914 < e$, obtenemos exponencial de la convergencia a $0$.

Por extraño $n$ el argumento es esencialmente el mismo, excepto que tenemos que considerar también la central de plazo (por $k = \frac{n}{2}+1$) por separado. \begin{eqnarray} \binom{n}{\frac{n}{2}+1} \left(c \frac{\frac{n}{2}+1}{2}\right)^{\frac{n}{2}+1} & \leq & 2^n \left( \sqrt{c \left(\frac{1}{2} + \frac{1}{n}\right)}\right)^n \cdot c \left(\frac{1}{2} + \frac{1}{n}\right) \\ & = & \left( \sqrt{c \left(2 + \frac{4}{n}\right)}\right)^n \cdot c \left(\frac{1}{2} + \frac{1}{n}\right). \end{eqnarray} Con $\sqrt{c \left(2 + \frac{4}{n}\right)} \approx 1.92828 < e$, el resultado sigue por extraño $n$.

Nota sobre la generalidad:

Así que, básicamente, si se desea estimar la asymptotics de $$ \frac{1}{x^n} \sum_{k=1}^n \binom{n}{k} \left(c\frac{k}{n}\right)^k, $$ el límite está garantizado para ser $0$ mientras $c \in [0,x-0.5)$.