Proof for any positive integer n the following equality hold

Question

$$\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?

Answer 1

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

Answer 2

$$S=\sum_{k=1}^{n} (-1)^k {n \choose k} \frac{1}{k}=\sum_{k=1}^{n} (-1)^k {n \choose k} \int_{0}^{1} t^{k-1} dt$$ $$= -\int_{0}^{1}\sum_{k=1}^{n}\frac{1}{t} {n \choose k} (-t)^k dt$$ $$=\int_{0}^{1} \frac{(1-t)^{n}-1}{(1-t)-1} dt =\int_{0}^{1} \frac{t^n-1}{t-1} dt$$ $$= \int_{0}^{1} [1+t+t^2+t^3+....t^{n-1}] dt= 1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$