Prove that $\sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k} = 1+\frac{1}{2}+...+\frac{1}{n}$

Question

How can I prove that $$\sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k} = 1+\frac{1}{2}+...+\frac{1}{n}.$$

I tried an induction but couldn't prove that $$\sum_{k=1}^{n+1} \frac{(-1)^{k-1}}{k} \binom{n+1}{k} = \frac{1}{n+1}+\sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k}.$$ Thanks.

Answer 1

In order to verify the inductive step, recall that $\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$. Therefore $$\begin{align}\sum_{k=1}^{n+1} \frac{(-1)^{k-1}}{k} \binom{n+1}{k}&= \sum_{k=1}^{n+1} \frac{(-1)^{k-1}}{k} \binom{n}{k-1}+ \sum_{k=1}^{n+1} \frac{(-1)^{k-1}}{k} \binom{n}{k}\\ &= \frac{1}{n+1}\sum_{k=1}^{n+1} (-1)^{k-1} \binom{n+1}{k}+ \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k}\\ &= \frac{1}{n+1}+ \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k} \end{align}$$ where at the last step we used $$1=1-(1-1)^{n+1}=\sum_{k=1}^{n+1} (-1)^{k-1} \binom{n+1}{k}.$$

Answer 2

Here's a well-known trick: \begin{align} \sum_{k=1}^n\frac{(-1)^{k-1}}k\binom{n}k&=\sum_{k=1}^n(-1)^{k-1}\binom{n}k \int_0^1 x^{k-1}\,dx=\int_0^1\frac{1-(1-x)^n}x\,dx\\ &=\int_0^1\frac{1-y^n}{1-y}\,dy=\sum_{k=1}^n\int_0^1 y^{k-1}\,dy =\sum_{k=1}^n\frac1k. \end{align}