Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
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
3  
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
1  
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

4 Answers 4

up vote 13 down vote accepted

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$

share|improve this answer
    
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
2  
... 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.

share|improve this answer
    
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}$.

share|improve this answer
    
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}}. $$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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