I wanted to compute the sum $$\sum_{k=1}^{n}\frac{1}{k}\binom{n}{k}.$$ And I thought it would be easiest to do this by making it a function, differentiating it and integrating it then.

So I did: $$f_n(a)=\sum_{k=1}^{n}\frac{1}{k}\binom{n}{k}a^k$$ $$f_n'(a)=\sum_{k=1}^{n}\binom{n}{k}a^{k-1}=\frac{(a+1)^n-1}{a}$$ And finally $$f_n(a)=\int\frac{(a+1)^n-1}{a}\mathrm{d}a+C(n)$$ where $C(n)$ is an unknown constant depending on $n$.

The first problem is the integral of course, so here it stops.

Can anyone help me calculating this integral or is there another way to calculate the sum?

EDIT: another approach:

I get, using Pascal's identity, $$S(n)=\sum_{k=1}^{n}\frac{1}{k}\binom{n}{k}=\frac{1}{n}+\sum_{k=1}^{n-1}\left(\frac{1}{k}\binom{n-1}{k-1}+\frac{1}{k}\binom{n-1}{k}\right)=\sum_{k=1}^{n}\frac{1}{n}\binom{n}{k}+\sum_{k=1}^{n-1}\frac{1}{k}\binom{n-1}{k}$$

So I have the recursion $S(n)=\frac{2^n-1}{n}+S(n-1)$, with $S(1)=\frac{2^1-1}{1}$.

Thus $$\sum_{k=1}^{n}\frac{1}{k}\binom{n}{k}=\sum_{k=1}^{n}\frac{2^k-1}{k}$$ if that might help.

Also, $f_n(a)=\displaystyle\sum_{k=1}^{n}\frac{(a+1)^k-1}{k}$ for the same reason.

  • $\begingroup$ It also appears to be the coefficient of $x^n$ in $-(1+x)^n\log(1-x)$ for $-1\le x<1$, don't know if this helps or not? $\endgroup$ – lab bhattacharjee Dec 3 '12 at 13:31
  • 1
    $\begingroup$ You can calculate the constant by regarding $f(0)$. $\endgroup$ – Phira Dec 3 '12 at 13:36
  • $\begingroup$ @Phira yes thanks. $\endgroup$ – punctured dusk Dec 3 '12 at 13:41
  • $\begingroup$ Essentially a duplicate of "The integral $\int_0^1 \frac{(x+1)^n-1}{x} dx$." The conclusion on that question is that there is no nice, simpler expression. $\endgroup$ – Mike Spivey Dec 3 '12 at 16:53

Here is a formula for the sum in terms of the hypergeometric function

$$\sum_{k=1}^{n}\frac{1}{k}\binom{n}{k}= n\, _3F_2(1,1,1-n;\,2,2;\,-1).$$

$$\,_3F_2(a_1,a_2,a_3;b_1,b_2;z) = \sum_{n=0}^\infty {(a_1)_n (a_2)_n (a_3)_n\over (b_1)_n (b_2)_n } \, {z^n \over n!} $$

  • $\begingroup$ I don't think that this really simplifies the sum, but I asked to 'rewrite' it, and that's what you did. Thanks anyway. $\endgroup$ – punctured dusk Dec 3 '12 at 13:42
  • $\begingroup$ @barto: Note that, not always possible to find simple forms for the sums. $\endgroup$ – Mhenni Benghorbal Dec 3 '12 at 13:45
  • $\begingroup$ I agree, but one can always try to. $\endgroup$ – punctured dusk Dec 3 '12 at 13:49

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.