9
$\begingroup$

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

(link to OEIS).

$\endgroup$
  • $\begingroup$ After plotting, a plausible asymptote seems to be (a constant times) $\exp(2n/3)$. But I am not confident of this. $\endgroup$ – S Huntsman Mar 29 '11 at 20:10
  • 3
    $\begingroup$ 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. $\endgroup$ – user940 Mar 29 '11 at 20:26
  • 1
    $\begingroup$ The OEIS link you gave has the $\sum (2^j -1)/j$ formula... $\endgroup$ – Aryabhata Mar 29 '11 at 21:23
  • $\begingroup$ @Moron: I see that now, didn't parse the a(n) properly. My apologies. $\endgroup$ – S Huntsman Mar 29 '11 at 22:12
  • $\begingroup$ No need to apologize :-) $\endgroup$ – Aryabhata Mar 29 '11 at 22:16
13
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Nice! $\endgroup$ – user940 Mar 29 '11 at 20:37
  • $\begingroup$ Oh, this is elegant. I'd considered Stirling but got caught up on something. But I didn't anticipate this. $\endgroup$ – S Huntsman Mar 29 '11 at 21:14
  • 2
    $\begingroup$ ... 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}}$ $\endgroup$ – Robert Israel Mar 29 '11 at 23:14
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I love this argument! $\endgroup$ – Raskolnikov Mar 29 '11 at 21:09
  • $\begingroup$ This is interesting, thanks. $\endgroup$ – S Huntsman Mar 29 '11 at 21:12
  • $\begingroup$ @Raskolnikov Thanks. It needs some work to make it rigorous though. $\endgroup$ – user940 Mar 29 '11 at 21:12
5
$\begingroup$

(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}$.

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

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

$\endgroup$
  • $\begingroup$ Another elegant answer! $\endgroup$ – S Huntsman Mar 29 '11 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.