5
$\begingroup$

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.

  • 0
    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?2012-12-03
  • 1
    You can calculate the constant by regarding $f(0)$.2012-12-03
  • 0
    @Phira yes thanks.2012-12-03
  • 0
    Essentially a duplicate of "[The integral $\int_0^1 \frac{(x+1)^n-1}{x} dx$](http://math.stackexchange.com/q/96287/)." The conclusion on that question is that there is no nice, simpler expression.2012-12-03

1 Answers 1

1

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

  • 0
    I don't think that this really simplifies the sum, but I asked to 'rewrite' it, and that's what you did. Thanks anyway.2012-12-03
  • 0
    @barto: Note that, not always possible to find simple forms for the sums.2012-12-03
  • 0
    I agree, but one can always try to.2012-12-03