Sum with binomial coefficients: $\sum_{k=1}^m \frac{1}{k}{m \choose k} $

I got this sum, in some work related to another question:

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

Are there any known results about this (bounds, asymptotics)?

You know that $\displaystyle (x + 1)^m = \sum_{k=0}^m {m \choose k} x^k$. So $$\int_0^1 \frac{(x + 1)^m - 1}{x} \, dx = \sum_{k=1}^m {m \choose k} \frac{1}{k}.$$

Letting $y = x + 1$ this is just $$\int_1^2 \frac{y^m - 1}{y - 1} \, dy = \sum_{k=1}^m \frac{2^k - 1}{k}.$$

The contribution of the $-1$ terms is $-H_m \sim - \log m$, so let's concentrate on estimating $$T_m = \sum_{k=1}^m \frac{2^k}{k}.$$

There is an obvious lower bound $$T_m \ge \sum_{k=1}^m \frac{2^k}{m} = \frac{2^{m+1} - 2}{m}.$$

To get an upper bound, we'll split the sum as $$\sum_{k=1}^{m-r} \frac{2^k}{k} + \sum_{k=m-r+1}^m \frac{2^k}{k}$$

for some $r$ (depending on $m$, although we do not specify the dependence for now). (Thanks to leonbloy for improvements in the part of the argument that follows!) Noting that $f(k) = \frac{2^k}{k}$ is an increasing function of $k$, the first part is bounded above by $(m-r) \frac{2^{m-r}}{m-r} = 2^{m-r}$ while the second is bounded above by $$\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}.$$ The first part gets smaller as $r$ increases while the second gets larger; to minimize their sum it is generally a good idea to make the two parts about as equal as possible. Thus we want $2^{m-r} \approx \frac{2^{m+1}}{m-r+1}$, or $$(m-r+1) \approx 2^{r+1}.$$

This gives $r \approx \log_2 m$. Setting $r = (1 + \epsilon) \log_2 m$ for some $\epsilon > 0$ makes the first part negligible relative to the second without really increasing the second and together with the lower bound gives an asymptotic $$T_m \sim \frac{2^{m+1}}{m}.$$

Edited by leonbloy: With respect to the upper bound - we have that, for any $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)$$

The expression in parentheses, thought as a function of $r$ (continuous), has a global minimum at $ 2^{r+1} = (m+1-r)^2 \log(2)$, which for large $m$ would give $r\approx 2 \log_2(m)$. Inspired by this, we can choose $r=\lceil 2 \log_2(m) \rceil$, and hence we can bound the two terms:

$$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) }$$

So, finally we have the bounds:

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

which, agrees with the above asymptotic.

I was following a path similar to @QiaochuYuan's, but he beat me to it!

Let's try another approach. If $m$ is large, we can use the de Moivre-Laplace theorem. Then $$\begin{equation*} S_m \simeq 2^m \int_1^\infty dk\, \frac{1}{\sqrt{2\pi}\sigma} e^{-(k-\mu)^2/(2\sigma^2)} \frac{1}{k}, \tag{1} \end{equation*}$$ where $\mu = m/2$ and $\sigma^2 = m/4$. (We have $p=q=1/2$.) The integral is dominated by $k\simeq \mu$. Therefore, $$\begin{eqnarray*} S_m &\simeq& 2^m \frac{2}{m} \int_1^\infty dk\, \frac{1}{\sqrt{2\pi}\sigma} e^{-(k-\mu)^2/(2\sigma^2)} \\ &\simeq& \frac{2^{m+1}}{m} \int_{-\infty}^\infty dk\, \frac{1}{\sqrt{2\pi}\sigma} e^{-(k-\mu)^2/(2\sigma^2)} \end{eqnarray*}$$ Thus, $$\begin{equation*} S_m \simeq \frac{2^{m+1}}{m}.\tag{2} \end{equation*}$$ This gives a good numerical approximation to the sum for large $m$.

We can get a better approximation by applying the saddle point method to (1). We find $$\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{equation*}$$

For $m=100$, (2) and (3) agree with the sum to $1\%$ and $0.03\%$, respectively.

We will make use of Euler-Maclaurin to get the asymptotic. The final asymptotic is $$\sum_{k=1}^{m} \dfrac1k\dbinom{m}{k} = \dfrac{2^{m+1}}{m} \left(\sum_{n=0}^{N} \dfrac{2^n \Gamma(n+1/2)}{m^n \sqrt{\pi}} \right) + \mathcal{O} \left( \dfrac{2^{m+1}}{m^{N+2}}\right)$$ Let us denote $\displaystyle \sum_{k=1}^{m} \dfrac1k\dbinom{m}{k}$ as $S$ i.e $$S = \sum_{k=1}^{m} \dfrac1k\dbinom{m}{k}$$ Let $f(k) = \dfrac1k$ and $A_m(k) = \displaystyle\sum_{n=1}^{k} \dbinom{m}{n}$. Hence, $$S = \sum_{k=1}^{m} f(n) \left( A_m(k) - A_m(k-1)\right) = \int_1^m f(t) dA_m(t) = \left. f(t)A_m(t) \right \rvert_{1}^m - \int_1^m A_m(t) df(t)\\ =\dfrac{2^m}{m} - \dfrac{m}{1} + \int_1^m \dfrac{A_m(t)}{t^2} dt$$ Now for large $m$, by central limit theorem, $$A_m(t) \sim \dfrac{2^m}{\sqrt{2 \pi \dfrac{m}4}} \int_1^t \exp \left( - \dfrac{(x-m/2)^2}{m/2}\right) dx = \dfrac{2^{m+1}}{\sqrt{2 \pi m}} \int_1^t \exp \left( - \dfrac{(x-m/2)^2}{m/2}\right) dx$$ Hence, we want an estimate for the integral $$I = \int_1^m \dfrac1{t^2} \int_1^t \exp \left( - \dfrac{(x-m/2)^2}{m/2}\right) dx \, dt$$ $$\int_1^m \int_x^m \dfrac1{t^2} \exp \left( - \dfrac{(x-m/2)^2}{m/2}\right) dt \, dx= \int_1^m \left( \dfrac1x - \dfrac1m \right) \exp \left( - \dfrac{(x-m/2)^2}{m/2}\right) dx$$ If we let $\dfrac{x-m/2}{\sqrt{m/2}} = y$, and let $s = \sqrt{m/2}$, then $$I = \displaystyle\int_{-s + 1/s}^{s} \left( \dfrac1{s^2 + ys} - \dfrac1{2s^2}\right) \exp(-y^2) s dy$$ $$I = \displaystyle\int_{-s + 1/s}^{s} \left( \dfrac1{s+y} - \dfrac1{2s}\right) \exp(-y^2) dy$$ $$I = \dfrac1s \displaystyle\int_{-s + 1/s}^{s} \left( \dfrac1{1+y/s} - \dfrac12\right) \exp(-y^2) dy$$ $$I = \dfrac1s \displaystyle\int_{-s + 1/s}^{s} \left( \dfrac12 - \dfrac{y}{s} + \dfrac{y^2}{s^2} - \dfrac{y^3}{s^3} + \dfrac{y^4}{s^4} \pm \cdots \right) \exp(-y^2) dy$$ For large $s$, $$\displaystyle \int_{-s+1/s}^s \exp(-y^2) dy = \sqrt{\pi} + \text{ some exponentially decaying error term}$$ $$\displaystyle \int_{-s+1/s}^s y \exp(-y^2) dy = 0 + \text{ some exponentially decaying error term}$$ $$\displaystyle \int_{-s+1/s}^s y^2 \exp(-y^2) dy = \dfrac{\sqrt{\pi}}{2} + \text{ some exponentially decaying error term}$$ $$\displaystyle \int_{-s+1/s}^s y^3 \exp(-y^2) dy = 0 + \text{ some exponentially decaying error term}$$ $$\displaystyle \int_{-s+1/s}^s y^4 \exp(-y^2) dy = \dfrac{3\sqrt{\pi}}{4} + \text{ some exponentially decaying error term}$$ Hence, $$I = \dfrac1s \left( \dfrac{\sqrt{\pi}}{2} + \dfrac{\sqrt{\pi}}{2s^2} + \dfrac{3 \sqrt{\pi}}{4s^4} + \mathcal{O} \left( \dfrac1{s^6} \right)\right)$$ Putting these together we get that $$S = \dfrac{2^m}{m} - m + \dfrac{2^{m+1}}{\sqrt{2 \pi m}} \times \left( \dfrac{\sqrt{2}}{\sqrt{m}} \left(\dfrac{\sqrt{\pi}}{2} + \dfrac{\sqrt{\pi}}{m} + \dfrac{3 \sqrt{\pi}}{m^2} + \mathcal{O} \left( \dfrac1{m^3} \right) \right)\right)$$ Hence, we get that $$S = \dfrac{2^m}{m} - m + \dfrac{2^{m+1}}{m} \times \left( \dfrac12 + \dfrac1m + \dfrac3{m^2} + \mathcal{O} \left( \dfrac1{m^3} \right) \right)$$ Hence, we get that $$S = \dfrac{2^{m+1}}{m} \left( 1 + \dfrac1m + \dfrac3{m^2} + \mathcal{O} \left(\dfrac1{m^3} \right) \right)$$ Extending this we see that $$S = \dfrac{2^{m+1}}{m} \left(\sum_{n=0}^{N} \dfrac{2^n \Gamma(n+1/2)}{m^n \sqrt{\pi}} \right) + \mathcal{O} \left( \dfrac{2^{m+1}}{m^{N+2}}\right)$$ i.e. writing out the first few terms, we get that $$S = \dfrac{2^{m+1}}{m} \left( 1 + \dfrac1m + \dfrac3{m^2} + \dfrac{15}{m^3} + \dfrac{105}{m^4} + \cdots \right)$$ One of the advantages is that it is easy to compute better asymptotic. The saddle method by oenamen can also be extended to get better asymptotic.