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)?
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\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\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*}$ 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.
Consider a random task as follows. First, one chooses a nonempty subset $X$ of $\{1,2,\ldots,m\}$, each with equal probability. Then, one uniformly randomly selects an element $n$ of $X$. The event of interest is when $n=\max(X)$.
Fix $k\in\{1,2,\ldots,m\}$. The probability that $|X|=k$ is $\frac{1}{2^m-1}\,\binom{m}{k}$. The probability that the maximum element of $X$, given $X$ with $|X|=k$, is chosen is $\frac{1}{k}$. Consequently, the probability that the desired event happens is given by $\sum_{k=1}^m\,\left(\frac{1}{2^m-1}\,\binom{m}{k}\right)\,\left(\frac{1}{k}\right)=\frac{S_m}{2^m-1}\,.$
Now, consider a fixed element $n\in\{1,2,\ldots,m\}$. Then, there are $\binom{n-1}{j-1}$ possible subsets $X$ of $\{1,2,\ldots,m\}$ such that $n=\max(X)$ and $|X|=j$. The probability of getting such an $X$ is $\frac{\binom{n-1}{j-1}}{2^m-1}$. The probability that $n=\max(X)$, given $X$, is $\frac{1}{j}$. That is, the probability that $n=\max(X)$ is $\begin{align} \sum_{j=1}^{n}\,\left(\frac{\binom{n-1}{j-1}}{2^m-1}\right)\,\left(\frac{1}{j}\right) &=\frac{1}{2^m-1}\,\sum_{j=1}^n\,\frac1j\,\binom{n-1}{j-1}=\frac{1}{2^m-1}\,\left(\frac{1}{n}\,\sum_{j=1}^n\,\frac{n}{j}\,\binom{n-1}{j-1}\right) \\ &=\frac{1}{2^m-1}\,\left(\frac{1}{n}\,\sum_{j=1}^n\,\binom{n}{j}\right)=\frac{1}{2^m-1}\left(\frac{2^n-1}{n}\right)\,. \end{align}$
Finally, it follows that $\frac{S_m}{2^m-1}=\sum_{n=1}^m\,\frac{1}{2^m-1}\left(\frac{2^n-1}{n}\right)$. Hence, $\sum_{k=1}^m\,\frac{1}{k}\,\binom{m}{k}=S_m=\sum_{n=1}^m\,\left(\frac{2^n-1}{n}\right)\,.$ It can then be shown by induction on $m>3$ that $\frac{2^{m+1}}{m}
A rather simple and gross bound is $\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$
Is there a "story" about $S_{m} = \sum_{k=1}^{m} \binom{m}{k}/k$ that would get to $\frac{2^{m+1}}{m}$ faster? For example, maybe the 2 expressions are approximately equivalent ways of counting something about the subsets of a set of cardinal $m$ as $m$ gets large. I'm struck by the fact that $\binom{m}{k}$ is the number of subsets of size $k$ of a set of size $m$, and $2^{m}$ is the number of subsets of a set of size $m$.