# What is the asymptotic behavior of A103213 in OEIS?

It's probably not at all hard—but at least right now it's not obvious to me—how to determine the asymptotic behavior of

$\sum_{k=1}^n \binom{n}{k} \frac{1}{k}$

-
After plotting, a plausible asymptote seems to be (a constant times) $\exp(2n/3)$. But I am not confident of this. –  S Huntsman Mar 29 '11 at 20:10
We have $$\sum_{k=1}^n {n\choose k}{1\over k} \geq \sum_{k=1}^n {n\choose k}{1\over k+1} = {2^{n+1}-2-n \over n+1}$$ so $\exp(2/3)$ is too small. –  Byron Schmuland Mar 29 '11 at 20:26
The OEIS link you gave has the $\sum (2^j -1)/j$ formula... –  Aryabhata Mar 29 '11 at 21:23
@Moron: I see that now, didn't parse the a(n) properly. My apologies. –  S Huntsman Mar 29 '11 at 22:12
No need to apologize :-) –  Aryabhata Mar 29 '11 at 22:16

Notice that $f(n) = \sum_{k=1}^n {n \choose k} \frac{1}{k} = \int_0^1 \frac{(t+1)^n - 1}{t}\, dt = \int_1^2 \frac{s^n - 1}{s-1} \, ds = \sum_{j=1}^{n} \frac{2^{j} - 1}{j}$. I think the leading term should be $2^{n+1}/n$

-
Nice! –  Byron Schmuland Mar 29 '11 at 20:37
Oh, this is elegant. I'd considered Stirling but got caught up on something. But I didn't anticipate this. –  S Huntsman Mar 29 '11 at 21:14
... and in fact I get $\frac{2^n}{n} (2 + \frac{2}{n} + \frac{6}{n^2} + \frac{26}{n^3} + \ldots) =$ (formally) $2^n \sum_{k=1}^\infty (-1)^k \frac{polylog(-k,2)}{n^{k+1}}$ –  Robert Israel Mar 29 '11 at 23:14

Here's a heuristic argument using probability.

Multiplying the OP's sum by $n/2^n$ gives $${1\over 2^n}\sum_{k=1}^n {n\choose k}{n\over k}=E\left({1\over \bar X_n}\right)$$ where $\bar X_n$ is the sample average of $n$ independent Bernoulli random variables with mean $1/2$ and we ignore the outcome $\bar X_n=0$.

By the law of large numbers, $1/\bar X_n\to 2$ almost surely, making it plausible that the left hand side of the equation above is approximately equal to 2.

-
I love this argument! –  Raskolnikov Mar 29 '11 at 21:09
This is interesting, thanks. –  S Huntsman Mar 29 '11 at 21:12
@Raskolnikov Thanks. It needs some work to make it rigorous though. –  Byron Schmuland Mar 29 '11 at 21:12

(see the related question)

Asymptotically, the sum behaves like the integral $$\sum_{k=1}^n \binom{n}{k} \frac{1}{k} = \int_1^n dk \, \frac{n!}{k! (n-k)! \,k}.$$ For large $n$, you can approximate the integral by expanding the integrand around its maximum (attained at $k=n/2$). We have (using Stirling) $$\log \frac{n!}{k! (n-k)!} \sim n \log n - k \log k -(n-k) \log (n-k)$$ with the maximum at $k=n/2$. The expansion around $k=n/2$ reads $$n \log n - k \log k -(n-k) \log (n-k) = - \frac{2}{n} (k- n/2)^2.$$ Thereby, we can approximate $$\sum_{k=1}^n \binom{n}{k} \frac{1}{k} \sim \frac{2}{n}\binom{n}{n/2} \int_1^n dk e^{ -2 (k- n/2)^2/n} \sim \frac{2}{n} \frac{2^n}{\sqrt{\pi n/2}} \sqrt{\frac{\pi n}{2}} =\frac{2^{n+1}}{n} ,$$ where we used the fact that $\binom{n}{n/2} \sim 2^n/\sqrt{\pi n/2}$.

-
Nice, my original thought was to use Stirling but I must have made a mistake en route. Thanks. –  S Huntsman Mar 29 '11 at 21:12
I believe this problem allows you to use the same technique. –  Douglas Zare Mar 29 '11 at 23:32

Here is an exact lower bound, which, as is readily seen, approximately equal to $2^{n+1}/n$. By Jensen's inequality, since $1/x$ is convex, $$\frac{{\sum\nolimits_{k = 1}^n {{n \choose k}} }}{{\sum\nolimits_{k = 1}^n {{n \choose k}} k}} \leq \frac{{\sum\nolimits_{k = 1}^n {{n \choose k}\frac{1}{k}} }}{{\sum\nolimits_{k = 1}^n {{n \choose k}} }}.$$ From this it follows straightforwardly that $$\frac{{(2^n - 1)^2 }}{{2^{n - 1} n}} \le \sum\limits_{k = 1}^n {{n \choose k}\frac{1}{k}} .$$

EDIT: Hence, $$\sum\limits_{k = 1}^n {{n \choose k}\frac{1}{k}} \geq \frac{{2^{n + 1} }}{n} - \frac{4}{n} + \frac{1}{{2^{n - 1} n}}.$$

-
Another elegant answer! –  S Huntsman Mar 29 '11 at 21:18
Thank you...... –  Shai Covo Mar 29 '11 at 21:22