7

I would like to find $\sum\limits_{k=1}^n \frac{1}{k}\binom{n}{k}$. I tried to write this as an integral but I can't find the result.

Watson
  • 23,793
Zhang Edison
  • 337
  • 2
    unluckily there is no simple closed form solution here...i guess you will need hypergeometric functions ^:( – tired Sep 26 '16 at 14:18
  • 2
    I agree with the above. By the Binomial theorem we can write this as an integral $\sum_{k=1}^n {n\choose k } \frac{1}{k} = \sum_{k=1}^n {n\choose k } \int_0^1x^{k-1}{\rm d}x = \int_0^1\frac{(1+x)^n-1}{x}{\rm d}x$ however evaluating this seems to require hypergeometrical functions. – Winther Sep 26 '16 at 14:20
  • @Winther Yeah that's where I got stuck too. Guess it's a problem within the question itself. – Zhang Edison Sep 26 '16 at 14:21
  • btw the identity we find $\sum_{n=1}^n{n\choose k} \frac{1}{k} = \int_1^2\frac{1-x^n}{1-x}{\rm d}x$ looks quite similar to $\sum_{k=1}^n(-1)^{k-1}{n\choose k}\frac{1}{k} = \int_0^1\frac{1-x^n}{1-x}{\rm d}x = H_n$ for the harmonic number. The latter does not have a closed form either. The integral we find is mentioned here ($a=2$). Mathematica gives the results as n HypergeometricPFQ[{1, 1, 1 - n}, {2, 2}, -1] which is $n , _3F_2(1,1,1-n;2,2;-1)$ in more standard notation. – Winther Sep 26 '16 at 14:31

1 Answers1

4

Let $$f(x)=\sum_{k=1}^n\frac1k{n\choose k}x^k$$ We are interested in $f(1)$ and note that $$ f'(x)=\sum_{k=1}^n{n\choose k}x^{k-1}=\frac1x\sum_{k=1}^n{n\choose k}x^{k}=\frac{(1+x)^n-1}{x}$$ so that $$f(1)=f(0)+\int_0^1f'(x)\,\mathrm dx=\int_0^1 \frac{(1+x)^n-1}{x}\,\mathrm dx$$

Hagen von Eitzen
  • 374,180
  • but this integral isn't really simpler then the original sum, right? – tired Sep 27 '16 at 11:20
  • Substitute $t = x+1$ in above and its easy to calculate the value then. – maverick Sep 27 '16 at 11:36
  • @maverick thanks for the hint, but i don't see how to obtain a result following this substitution – tired Sep 27 '16 at 11:52
  • 2
    by the way, the integral representation enables us to give a nice asymptotic estimate for the sum: $S_n\sim \frac{2^{n+1}}{n+1}$ – tired Sep 27 '16 at 11:54