Calculate $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$ [duplicate]

Calculate $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$, I do not know hot get rid of that $k$, for me it is similar like $\binom{n}{k}=\frac{k}{n} \binom{n-1}{k-1}$, do you have some idea?

Solution 1:

Hint. There is no closed formula here. Compute the first few terms and compare them with the $n$th-harmonic number $H_n=\sum_{k=1}^n\frac{1}{k}$. What can we conjecture?

P.S. BTW the linked sum $\sum(-1)^k{n\choose k}\frac{1}{k+1}$ is "similar" but quite much easier (it has a closed formula).

Solution 2:

We can write your sum as $$ \eqalign{ & f(n) = \sum\limits_{k = 1}^n {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n \cr k \cr} \right){1 \over k}} = \cr & = \sum\limits_{k = 0}^{n - 1} {\left( { - 1} \right)^{\,k} \left( \matrix{ n \cr k + 1 \cr} \right){1 \over {k + 1}}} = \sum\limits_{k = 0}^\infty {\left( { - 1} \right)^{\,k} \left( \matrix{ n \cr k + 1 \cr} \right){1 \over {k + 1}}} = \cr & = \sum\limits_{k = 0}^\infty {t_k } \cr} $$

and we can express it in terms of a Hypergeometric function, since $$ \eqalign{ & t_0 = \left( \matrix{ n \cr 1 \cr} \right) = n \cr & {{t_{k + 1} } \over {t_k }} = - {{n^{\,\underline {\,k + 2\,} } } \over {\left( {k + 2} \right)\left( {k + 2} \right)!}} {{\left( {k + 1} \right)\left( {k + 1} \right)!} \over {n^{\,\underline {\,k + 1\,} } }} = \cr & = - {{\left( {n - 1 - k} \right)} \over 1}{{\left( {k + 1} \right)} \over {\left( {k + 2} \right)\left( {k + 2} \right)}} = {{\left( {k - n + 1} \right)\left( {k + 1} \right)} \over {\left( {k + 2} \right)\left( {k + 2} \right)}} \cr} $$

Then $$ f(n) = n\;{}_3F_2 \left( {\left. {\matrix{ { - n + 1,\;1,\;1} \cr {2,\;2} \cr } \;} \right|\;1} \right) $$

Alternatively, we have that $$ \eqalign{ & f(n + 1) = \sum\limits_{k = 1}^{n + 1} {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n + 1 \cr k \cr} \right){1 \over k}} = \cr & = \left( {\sum\limits_{k = 1}^{n + 1} {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n \cr k \cr} \right){1 \over k}} + \sum\limits_{k = 1}^{n + 1} {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n \cr k - 1 \cr} \right){1 \over k}} } \right) = \cr & = \left( {\sum\limits_{k = 1}^{n + 1} {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n \cr k \cr} \right){1 \over k}} + {1 \over {n + 1}}\sum\limits_{k = 1}^{n + 1} {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n + 1 \cr k \cr} \right)} } \right) = \cr & = \sum\limits_{k = 1}^n {\left( { - 1} \right)^{\,k + 1} \left( \matrix{ n \cr k \cr} \right){1 \over k}} - {1 \over {n + 1}}\left( {0^{\,n + 1} - 1} \right) = \cr & = f(n) + {1 \over {n + 1}} \cr} $$ i.e.: $$ \left\{ \matrix{ f(0) = 0 \hfill \cr f(1) = 1 \hfill \cr f(n + 1) - f(n) = \Delta f(n) = {1 \over {n + 1}} \hfill \cr} \right. $$

or $$ \left\{ \matrix{ g(n) = n!f(n) \hfill \cr g(0) = 0 \hfill \cr g(1) = 1 \hfill \cr g(n + 1) = \left( {n + 1} \right)f(n) + n! \hfill \cr} \right. $$ and this is the recurrence satified by $$g(n)=\left[ \matrix{ n+1 \cr 2 \cr} \right]$$ where $\left[ \matrix{ n \cr m \cr} \right]$ represents the (unsigned) Stirling number of 1st kind.

Thus $$ \bbox[lightyellow] { f(n) = \sum\limits_{k = 1}^n {\left( { - 1} \right)^{\,k + 1} \binom{n}{k}{1 \over k}} = {1 \over {n!}}\left[ \matrix{ n + 1 \cr 2 \cr} \right] }$$

Also refer to OEIS seq. A000254 .

Solution 3:

This problem and its type appear at MSE regularly. Suppose we seek to compute

$$S_n = \sum_{k=1}^n {n\choose k} \frac{(-1)^{k+1}}{k}.$$

With this in mind we introduce the function

$$f(z) = n! (-1)^{n+1} \frac{1}{z^2} \prod_{q=1}^n \frac{1}{z-q}.$$

We then obtain for $1\le k\le n$

$$\mathrm{Res}_{z=k} f(z) = (-1)^{n+1} \frac{n!}{k^2} \prod_{q=1}^{k-1} \frac{1}{k-q} \prod_{q=k+1}^n \frac{1}{k-q} \\ = (-1)^{n+1} \frac{n!}{k} \frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!} = {n\choose k} \frac{(-1)^{k+1}}{k}.$$

This means that

$$S_n = \sum_{k=1}^n \mathrm{Res}_{z=k} f(z)$$

and since residues sum to zero we have

$$S_n + \mathrm{Res}_{z=0} f(z) + \mathrm{Res}_{z=\infty} f(z) = 0.$$

We can compute the residue at infinity by inspection (it is zero) or more formally through

$$\mathrm{Res}_{z=\infty} n! (-1)^{n+1} \frac{1}{z^2} \prod_{q=1}^n \frac{1}{z-q} \\ = - n! (-1)^{n+1} \mathrm{Res}_{z=0} \frac{1}{z^2} z^2 \prod_{q=1}^n \frac{1}{1/z-q} \\ = - n! (-1)^{n+1} \mathrm{Res}_{z=0} \prod_{q=1}^n \frac{z}{1-qz} \\ = - n! (-1)^{n+1} \mathrm{Res}_{z=0} z^n \prod_{q=1}^n \frac{1}{1-qz} = 0.$$

We get for the residue at $z=0$ that

$$\mathrm{Res}_{z=0} f(z) = n! (-1)^{n+1} \left. \left(\prod_{q=1}^n \frac{1}{z-q}\right)'\right|_{z=0} \\ = - n! (-1)^{n+1} \left. \left(\prod_{q=1}^n \frac{1}{z-q}\right) \sum_{q=1}^n \frac{1}{z-q} \right|_{z=0} \\ = n! (-1)^n \frac{(-1)^{n}}{n!} \left(-H_{n}\right) = -H_n.$$

We thus have $S_n - H_n = 0$ or

$$\bbox[5px,border:2px solid #00A000]{ S_n = H_n = \sum_{k=1}^n \frac{1}{k}.}$$