Pruebas de $\lim\limits_{n \to \infty} \left(H_n - 2^{-n} \sum\limits_{k=1}^n \binom{n}{k} H_k\right) = \log 2$

Question

Dejemos que $H_n$ denotan el $n$ número armónico; es decir, $H_n = \sum\limits_{i=1}^n \frac{1}{i}$ . Tengo un par de pruebas de la siguiente expresión limitadora, que no creo que sea tan conocida: $$\lim_{n \to \infty} \left(H_n - \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} H_k \right) = \log 2.$$ Tengo curiosidad por conocer otras formas de demostrar esta expresión, así que he pensado en preguntar aquí para ver si alguien conoce alguna o se le ocurre alguna. En particular, me gustaría ver una prueba combinatoria, pero eso podría ser difícil dado que estamos tomando un límite y tenemos un número trascendental en un lado. Sin embargo, me gustaría ver cualquier prueba. No publicaré las mías durante uno o dos días para dar a los demás la oportunidad de responder primero.

(La etiqueta de probabilidad se incluye porque la expresión cuyo límite se está tomando también puede interpretarse de forma probabilística).

---

( Añadido : He aceptado la primera respuesta de Srivatsan, y he colgado mis dos pruebas para los que estén interesados en verlas.

También puede ser interesante la pregunta inversa. Supongamos que tenemos una función $f(n)$ tal que $$\lim_{n \to \infty} \left(f(n) - \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} f(k) \right) = L,$$ donde $L$ es finito y distinto de cero. ¿Qué podemos decir sobre $f(n)$ ? Esta pregunta fue formulada y respondió hace un tiempo ; resulta que $f(n)$ debe ser $\Theta (\log n)$ . Más concretamente, debemos tener $\frac{f(n)}{\log_2 n} \to L$ como $n \to \infty$ .)

Answer 1

He hecho una estimación rápida en mi comentario. La idea básica es que la distribución binomial $2^{n} \binom{n}{k}$ se concentra en torno a $k= \frac{n}{2}$ . Simplemente introduciendo este valor en la expresión del límite, obtenemos $H_nH_{n/2} \sim \ln 2$ para grandes $n$ . Afortunadamente, formalizar la intuición no es tan difícil.

Llama a la suma gigante $S$ . Observe que $S$ puede escribirse como $\newcommand{\E}{\mathbf{E}}$ $$ \sum_{k=0}^{\infty} \frac{1}{2^{n}} \binom{n}{k} (H(n) - H(k)) = \sum_{k=0}^{\infty} \Pr[X = k](H(n) - H(k)) = \E \left[ H(n) - H(X) \right], $$ donde $X$ se distribuye según la distribución binomial $\mathrm{Bin}(n, \frac12)$ . Necesitamos los siguientes dos datos sobre $X$ :

• Con probabilidad $1$ , $0 \leqslant H(n) - H(X) \leqslant H(n) = O(\ln n)$ .
• Desde el La desigualdad de Bernstein para cualquier $\varepsilon \gt 0$ sabemos que $X$ se encuentra en el rango $\frac{1}{2}n (1\pm \varepsilon)$ excepto con una probabilidad máxima de $e^{- \Omega(n \varepsilon^2) }$ .

Dado que la función $x \mapsto H(n) - H(x)$ es monótona decreciente, tenemos $$ S \leqslant \color{Red}{H(n)} \color{Blue}{-H\left( \frac{n(1-\varepsilon)}{2} \right)} + \color{Green}{\exp (-\Omega(n \varepsilon^2)) \cdot O(\ln n)}. $$ Introduciendo la estimación estándar $H(n) = \ln n + \gamma + O\Big(\frac1n \Big)$ para la suma armónica, obtenemos: $$ \begin{align*} S &\leqslant \color{Red}{\ln n + \gamma + O \Big(\frac1n \Big)} \color{Blue}{- \ln \left(\frac{n(1-\varepsilon)}{2} \right) - \gamma + O \Big(\frac1n \Big)} +\color{Green}{\exp (-\Omega(n \varepsilon^2)) \cdot O(\ln n)} \\ &\leqslant \ln 2 - \ln (1- \varepsilon) + o_{n \to \infty}(1) \leqslant \ln 2 + O(\varepsilon) + o_{n \to \infty}(1). \tag{1} \end{align*} $$

Un argumento análogo obtiene el límite inferior $$ S \geqslant \ln 2 - \ln (1+\varepsilon) - o_{n \to \infty}(1) \geqslant \ln 2 - O(\varepsilon) - o_{n \to \infty}(1). \tag{2} $$ Dado que las estimaciones $(1)$ y $(2)$ mantener para todos $\varepsilon > 0$ se deduce que $S \to \ln 2$ como $n \to \infty$ .

Answer 2

Aquí tenemos una prueba diferente. Simplificaremos el segundo término como sigue: $$ \begin{eqnarray*} \frac{1}{2^n} \sum\limits_{k=0}^n \left[ \binom{n}{k} \sum\limits_{t=1}^{k} \frac{1}{t} \right] &=& \frac{1}{2^n} \sum\limits_{k=0}^n \left[ \binom{n}{k} \sum\limits_{t=1}^{k} \int_{0}^1 x^{t-1} dx \right] \\ &=& \frac{1}{2^n} \int_{0}^1 \sum\limits_{k=0}^n \left[ \binom{n}{k} \sum\limits_{t=1}^{k} x^{t-1} \right] dx \\ &=& \frac{1}{2^n} \int_{0}^1 \sum\limits_{k=0}^n \left[ \binom{n}{k} \cdot \frac{x^k-1}{x-1} \right] dx \\ &=& \frac{1}{2^n} \int_{0}^1 \frac{\sum\limits_{k=0}^n \binom{n}{k} x^k- \sum\limits_{k=0}^n \binom{n}{k}}{x-1} dx \\ &=& \frac{1}{2^n} \int_{0}^1 \frac{(x+1)^n- 2^n}{x-1} dx. \end{eqnarray*} $$

Realice la sustitución $y = \frac{x+1}{2}$ Así que los nuevos límites son ahora $1/2$ y $1$ . La integral cambia entonces a: $$ \begin{eqnarray*} \int_{1/2}^1 \frac{y^n- 1}{y-1} dy &=& \int_{1/2}^1 (1+y+y^2+\ldots+y^{n-1}) dy \\ &=& \left. y + \frac{y^2}{2} + \frac{y^3}{3} + \ldots + \frac{y^n}{n} \right|_{1/2}^1 \\ &=& H_n - \sum_{i=1}^n \frac{1}{i} \left(\frac{1}{2} \right)^i. \end{eqnarray*} $$ Observe que convenientemente $H_n$ es el primer término de nuestra función. Reordenando, la expresión bajo el límite es igual a: $$ \sum_{i=1}^n \frac{1}{i} \left(\frac{1}{2} \right)^i. $$ El último paso es observar que esto es sólo el $n$ La suma parcial de la expansión en serie de Taylor de $f(y) = -\ln(1-y)$ en $y=1/2$ . Por lo tanto, como $n \to \infty$ esta secuencia se aproxima al valor $$-\ln \left(1-\frac{1}{2} \right) = \ln 2.$$

AÑADIDO: Como se desprende de los comentarios de Didier, esta prueba también muestra que la secuencia dada, llámese $u_n$ es monotónica y, por tanto, siempre es menor que $\ln 2$ . Además, también tenemos una estimación de error ajustada: $$ \frac{1}{n2^n} < \ln 2 - u_n < \frac{2}{n2^n}, \ \ \ \ (n \geq 1). $$

Answer 3

Aquí están mis dos pruebas, por si alguien está interesado.

---

Prueba 1 : El $n$ El término es $\sum_{k=1}^n \frac{1}{k 2^k}$ .

Dejemos que $\Delta f(k) = f(k+1) - f(k)$ es decir, la diferencia finita de $f(k)$ .

Dejemos que $B(n) = \sum_{k=0}^n \binom{n}{k} f(k)$ , $A(n) = \sum_{k=0}^n \binom{n}{k} \Delta f(k)$ .

Hace unos años probé $^1$ la siguiente relación entre $B(n)$ y $A(n)$ :

$$B(n) = 2^n \left(f(0) + \sum_{k=1}^n \frac{A(k-1)}{2^k}\right).$$

Ahora, $\Delta H_n = \frac{1}{n+1}$ . Y sabemos que

$$\sum_{k=0}^n \binom{n}{k} \frac{1}{k+1} = \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1} = \frac{2^{n+1}-1}{n+1},$$ utilizando el hecho de que $\binom{n}{k} \frac{n+1}{k+1} = \binom{n+1}{k+1}$ .

Por lo tanto, la fórmula anterior para $B(n)$ produce

$$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \sum_{k=1}^n \frac{2^k-1}{k2^k} = 2^n\left(H_n - \sum_{k=1}^n \frac{1}{k2^k}\right).$$

Reordenando, obtenemos $$H_n - \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} H_k = \sum_{k=1}^n \frac{1}{k 2^k}.$$

Así, $$\lim_{n \to \infty} \left(H_n - \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} H_k\right) = \sum_{k=1}^{\infty} \frac{1}{k 2^k} = \log 2,$$ donde el $\log 2$ se obtiene, como en la segunda respuesta de Srivatsan, sustituyendo $-1/2$ en la serie Maclaurin para $\log(1+x)$ .

(Así es como me encontré por primera vez con el resultado del límite; estaba tratando de encontrar una expresión para $\sum_{k=0}^n \binom{n}{k} H_k$ .)

$^1$ " Sumas combinatorias y diferencias finitas ," Matemáticas discretas, 307 (24): 3130-3146, 2007.

---

Prueba 2 : El argumento probabilístico.

Dejemos que $X_1, X_2, \ldots, X_n$ sea $n$ variables aleatorias exponenciales independientes e idénticamente distribuidas con parámetro de tasa $\lambda$ . El mínimo de estos $n$ variables aleatorias es conocido para tener un exponencial $n \lambda$ distribución. Sea $X_{(k)}$ denotan el $k$ más pequeño. Debido a la propiedad sin memoria de la distribución exponencial, $X_{(k+1)} - X_{(k)}$ tiene un exponencial $(n-k) \lambda$ distribución. Así que $E[X_{(k+1)} - X_{(k)}] = \frac{1}{(n-k)\lambda}$ . Dejemos que $Y_n = X_{(n)}$ (es decir, el más grande). Así, $$E[Y_n] = \sum_{k=0}^{n-1} E[(X_{(k+1)} - X_{(k)})= \sum_{k=1}^n \frac{1}{\lambda k} = \frac{H_n}{\lambda}.$$

Ahora, considere $E[Y_n | Y_n > 1]$ . Desde $P(X_i < 1) = 1-e^{-\lambda}$ condicionando el número de la $X_i$ con valores inferiores a $1$ produce $$E[Y_n | Y_n > 1] = 1 + \sum_{k=0}^{n-1} \binom{n}{k} \left(1 - e^{-\lambda}\right)^k \left(e^{-\lambda}\right)^{n-k} \frac{H_{n-k}}{\lambda}$$ $$= 1 + \sum_{k=1}^n \binom{n}{k} \left(1 - e^{-\lambda}\right)^{n-k} \left(e^{-\lambda}\right)^k \frac{H_k}{\lambda}.$$

Pero como $n \to \infty$ , $E[Y_n] - E[Y_n|Y_n > 1] \to 0$ ya que $P(Y_n > 1) = 1 - e^{-\lambda n}$ . Por lo tanto, $$\lim_{n \to \infty} \left(\frac{H_n}{\lambda} - \sum_{k=1}^n \binom{n}{k} \left(1 - e^{-\lambda}\right)^{n-k} \left(e^{-\lambda}\right)^k \frac{H_k}{\lambda}\right) = 1.$$

Dejar $\lambda = \log 2$ da el resultado.

Answer 4

Mirando $2^{-n}\binom{n}{k}$ como una distribución de probabilidad con media $\frac{n}{2}$ y la desviación estándar $\frac{\sqrt{n}}{2}$ es bastante fácil ver que, como suma de Riemann $$ \begin{align} 2^{-n}\sum_{k=1}^n\binom{n}{k}H_k&\sim\sqrt{\frac{2}{\pi n}}\int_{-\infty}^\infty (\log(x)+\gamma)\;e^{-2(x-n/2)^2/n}\;\mathrm{d}x\\ &=\log(n/2)+\gamma+O\left(\frac{1}{\sqrt{n}}\right) \end{align} $$ Desde $H_n\sim\log(n)+\gamma$ obtenemos que la diferencia sea $\log(2)$ .

Permítanme atacar esto de una manera diferente (aunque la primera sigue funcionando).

Utilizando la expansión asintótica para $H_n$ obtenemos para $k\le n$ , $$ H_n-H_k=-\log(k/n)+O\left(\frac{1}{k}\right)\tag{1} $$ Dado que vamos a tratar con $O\left(\frac{1}{k}\right)$ , fíjese que $$ \begin{align} 2^{-n}\sum_{k=1}^n\binom{n}{k}\frac{1}{k+1} &=2^{-n}\sum_{k=1}^n\binom{n+1}{k+1}\frac{1}{n+1}\\ &\le 2^{-n}\;2^{n+1}\frac{1}{n+1}\\ &=\frac{2}{n+1} \end{align} $$ Por lo tanto, $$ 2^{-n}\sum_{k=1}^n\binom{n}{k}O\left(\frac{1}{k+1}\right)=O\left(\frac{1}{n+1}\right)\tag{2} $$ El Teorema del Límite Central dice que para cualquier continuo $f$ en $[0,1]$ , $$ \lim_{n\to\infty}\;2^{-n}\sum_{k=1}^n\binom{n}{k}f\left(\frac{k}{n}\right) = f\left(\frac{1}{2}\right)\tag{3} $$ Para justificar $(3)$ , elige $\epsilon>0$ y encontrar $\delta$ para que $\left|x-\frac{1}{2}\right|<\delta\Rightarrow\left|f(x)-f(\frac{1}{2})\right|<\epsilon$ . Porque la media de $2^{-n}\binom{n}{k}$ es $\frac{n}{2}$ y la varianza es $\frac{n}{4}$ el Teorema Central del Límite dice que podemos elegir un $\sigma$ lo suficientemente grande como para que $$ \underset{|k-n/2|<\sigma\sqrt{n}/2}{2^{-n}\sum\binom{n}{k}}>1-\epsilon $$ para todos $n$ . Por lo tanto, elegimos un $n$ lo suficientemente grande como para que $\sigma\sqrt{n}/2<n\delta$ . $$ \begin{align} 2^{-n}\sum_{k=1}^n\binom{n}{k}\left|f\left(\frac{k}{n}\right)-f\left(\frac{1}{2}\right)\right| &\le \epsilon\;\max_{[0,n]}\left|f\left(\frac{k}{n}\right)-f\left(\frac{1}{2}\right)\right|\\ &+\max_{|k-n/2|<n\delta}\left|f\left(\frac{k}{n}\right)-f\left(\frac{1}{2}\right)\right|\\ &\le \epsilon\;\max_{[0,1]}\left|f\left(x\right)-f\left(\frac{1}{2}\right)\right|\\ &+\;\epsilon \end{align} $$

Finalmente, $$ \begin{align} H_n-2^{-n}\sum_{k=0}^n\binom{n}{k}H_k &=2^{-n}\sum_{k=0}^n\binom{n}{k}(H_n-H_k)\\ &=2^{-n-1}\sum_{k=0}^n\binom{n+1}{k+1}\;2\frac{k+1}{n+1}(H_n-H_k)\\ &=2^{-n-1}\sum_{k=0}^n\binom{n+1}{k+1}\left(-2\frac{k+1}{n+1}\log\left(\frac{k+1}{n+1}\right)+O\left(\frac{1}{k+1}\right)\right)\\ &=-2^{-n-1}\sum_{k=0}^n\binom{n+1}{k+1}\left(-2\frac{k+1}{n+1}\log\left(\frac{k+1}{n+1}\right)\right)+O\left(\frac{1}{n+1}\right)\\ &\to-2\;\frac{1}{2}\log(\frac{1}{2})\\[9pt] &=\log(2) \end{align} $$

Answer 5

$H_{n+1} - \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} H_k \quad $ es el valor esperado de $(\sum_{i=j}^{n+1} 1/i)$ donde $j$ es la posición de un paseo aleatorio iniciado en $j=1$ y con $j$ tomando $n$ pasos de +0 o +1 cada uno con probabilidad 1/2.

El límite es el mismo que para la expresión original con $H_n$ y equivale a la afirmación de que $j$ es (con una probabilidad cercana a 1 como $n$ aumenta) concentrado en un intervalo de longitud $o(n)$ alrededor de $n/2$ . Esto es mucho más débil que el Teorema Central del Límite y se mantendría para paseos aleatorios bastante generales con velocidad media +1/2.