Proof for any positive integer n the following equality hold $$\sum_{k=1}^n (-1)^{k+1} \binom {n}{k} \frac{1}{k}= 1 + \frac{1}{2} + ...  + \frac{1}{n}$$
How do I prove this by induction? 
My attempt: let $n = 1$, then $(-1)^2 \binom{1}{k} =1=\frac{1}{1}$
Assuming $n$ is true, how do I prove the $n + 1$ case?

The induction strategy is: suppose that the result holds for $n\geq 1$, and we want to show that it holds for $n+1$. The solution I came up with uses a few classic results about binomial coefficients (see here if you want). Try using the recursion formula $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$ and then the "absorption" formula $$\binom{n+1}{k}=\frac{n+1}{k}\binom{n}{k-1}$$ and then $$\sum_{k=0}^{n+1} (-1)^k\binom{n+1}{k}=0.$$
Spoiler:

 $$\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}+\sum_{k=1}^{n+1} \frac{(-1)^{k+1}}{k}\binom{n}{k-1} \\&= \left[1+\frac{1}{2}+\cdots+\frac{1}{n}\right]+\frac{1}{n+1}\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n+1}{k} \\&= \left[1+\frac{1}{2}+\cdots+\frac{1}{n}\right]+\frac{1}{n+1}\left[\binom{n+1}{0}-\sum_{k=0}^{n+1}(-1)^{k}\binom{n+1}{k}\right] \\&= \left[1+\frac{1}{2}+\cdots+\frac{1}{n}\right]+\frac{1}{n+1}\binom{n+1}{0} \\&= 1+\frac{1}{2}+\cdots+\frac{1}{n}+\frac{1}{n+1}.\end{align}$$


Just in case you don't believe me on the above formulae: you can prove the first two just using $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ pretty easily, and the last one follows from binomial theorem by considering $0=(1-1)^{n+1}$.
