<s>[INST] Prove that $\sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k} = 1+\frac{1}{2}+...+\frac{1}{n}$ 
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.
 [/INST] 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}.$$
</s>