<s>[INST] 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)? 
 [/INST] 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.
</s>