Suma con coeficientes binomiales: $\sum_{k=1}^m \frac{1}{k}{m \choose k} $

Question

Tengo esta suma, en algunos trabajos relacionados con otra pregunta:

$$S_m=\sum_{k=1}^m \frac{1}{k}{m \choose k} $$

¿Hay cualquier resultados conocidos sobre este (bounds, multicelular)?

Answer 1

Usted sabe que $\displaystyle (x + 1)^m = \sum_{k=0}^m {m \choose k} x^k$. Así $$\int_0^1 \frac{(x + 1)^m - 1}{x} \, dx = \sum_{k=1}^m {m \choose k} \frac{1}{k}.$$

Dejando $y = x + 1$ esto es sólo $$\int_1^2 \frac{y^m - 1}{y - 1} \, dy = \sum_{k=1}^m \frac{2^k - 1}{k}.$$

La contribución de la $-1$ condiciones es $-H_m \sim - \log m$, así que vamos a concentrarnos en la estimación de $$T_m = \sum_{k=1}^m \frac{2^k}{k}.$$

Es evidente que existe una cota inferior $$T_m \ge \sum_{k=1}^m \frac{2^k}{m} = \frac{2^{m+1} - 2}{m}.$$

Para obtener una cota superior, vamos a dividir la suma como $$\sum_{k=1}^{m-r} \frac{2^k}{k} + \sum_{k=m-r+1}^m \frac{2^k}{k}$$

para algunos $r$ (dependiendo $m$, aunque no se especifica la dependencia, por ahora). (Gracias a leonbloy para mejoras en la parte del argumento que sigue!) Tomando nota de que $f(k) = \frac{2^k}{k}$ es una función creciente de $k$, la primera parte está acotada arriba por $(m-r) \frac{2^{m-r}}{m-r} = 2^{m-r}$, mientras que el segundo está acotada arriba por $$\sum_{k=m-r+1}^m \frac{2^k}{m-r+1} \le \frac{1}{m-r+1} \sum_{k=0}^m 2^k < \frac{2^{m+1}}{m-r+1}.$$ La primera parte se hace menor a lo $r$ aumenta mientras que la segunda se hace más grande; para minimizar la suma de los mismos es generalmente una buena idea para hacer que las dos partes acerca de tan iguales como sea posible. Por lo tanto queremos que $2^{m-r} \approx \frac{2^{m+1}}{m-r+1}$, o $$(m-r+1) \approx 2^{r+1}.$$

Esto le da a $r \approx \log_2 m$. Establecimiento $r = (1 + \epsilon) \log_2 m$ algunos $\epsilon > 0$ hace que la primera parte insignificante en comparación con el segundo sin aumentar el segundo, y junto con el límite inferior le da un asintótica $$T_m \sim \frac{2^{m+1}}{m}.$$

Editado por leonbloy: Con respecto al límite superior -, tenemos que, para cualquier $r = 1..m$:

$$T_m \le 2^{m-r} + \frac{2^{m+1}}{m-r+1} = 2^m \left(2^{-r} + \frac{2}{m-r+1}\right)$$

La expresión entre paréntesis, el pensamiento como una función de $r$ (continuo), tiene un mínimo global en $ 2^{r+1} = (m+1-r)^2 \log(2)$, que para un gran $m$ daría $r\approx 2 \log_2(m)$. Inspirado por esto, podemos optar $r=\lceil 2 \log_2(m) \rceil$, y de ahí que podamos enlazado los dos términos:

$$r \ge 2 \log_2(m) \Rightarrow 2^{-r} \le \frac{1}{m^2}$$

$$r \le 2 \log_2(m) +1 \Rightarrow \frac{2}{m-r+1} \le \frac{2}{m-2 \log_2(m) }$$

Así que, finalmente tenemos los límites:

$$ \frac{2}{m}(1+ 2^{-m}) \le \frac{T_m}{2^{m}} \le \frac{2}{m-2 \log_2(m) } +\frac{1}{m^2} $$

que, de acuerdo con el de arriba asintótica.

Answer 2

Yo estaba siguiendo un camino similar al de @QiaochuYuan, pero él me pegaba a él!

Vamos a intentarlo de otra forma. Si $m$ es grande, podemos utilizar el de Moivre-Laplace teorema. Entonces $$\begin{equation*} S_m \simeq 2^m \int_1^\infty dk\, \frac{1}{\sqrt{2\pi}\sigma} e^{-(k-\mu)/(2\sigma^2)} \frac{1}{k}, \tag{1} \end{ecuación*}$$ donde$\mu = m/2$$\sigma^2 = m/4$. (Tenemos $p=q=1/2$.) La integral es dominado por $k\simeq \mu$. Por lo tanto, $$\begin{eqnarray*} S_m &\simeq& 2^m \frac{2}{m} \int_1^\infty dk\, \frac{1}{\sqrt{2\pi}\sigma} e^{-(k-\mu)/(2\sigma^2)} \\ &\simeq& \frac{2^{m+1}}{m} \int_{-\infty}^\infty dk\, \frac{1}{\sqrt{2\pi}\sigma} e^{-(k-\mu)/(2\sigma^2)} \end{eqnarray*}$$ Por lo tanto, $$\begin{equation*} S_m \simeq \frac{2^{m+1}}{m}.\tag{2} \end{ecuación*}$$ Esto le da una buena aproximación numérica a la suma de un gran $m$.

Podemos obtener una mejor aproximación mediante la aplicación de la silla de montar método de punto a (1). Nos encontramos $$\begin{equation*} S_m \simeq \frac{2^{m+1}}{m} \left(1+\frac{1}{m} + O\left(\frac{1}{m^2}\right)\right).\tag{3} \end{ecuación*}$$

Para $m=100$, (2) y (3) de acuerdo con la suma de los $1\%$$0.03\%$, respectivamente.

Answer 3

Un límite algo simple y el bruto es $$\sum_{k=1}^m\frac{1}{k}\binom{m}{k}\leq\sum_{k=1}^m\binom{m}{k}<\sum_{k=0}^m\binom{m}{k}=2^m$ $

Answer 4

¿Hay una "historia" de $S_{m} = \sum_{k=1}^{m} \binom{m}{k}/k$ que $\frac{2^{m+1}}{m}$ más rápido? Por ejemplo, tal vez las 2 expresiones son aproximadamente equivalentes formas de contar algo acerca de los subconjuntos de un conjunto de cardinal $m$, $m$ crece. Me llama la atención el hecho de que $\binom{m}{k}$ es el número de subconjuntos de tamaño $k$ de un conjunto de tamaño $m$ $2^{m}$ es el número de subconjuntos de un conjunto de tamaño $m$.