Prove by induction: $\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$

Question

$\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$

For $n=1$ equality is true.

For $n=m$

$m-{m\choose 2}\frac{1}{2}+...+(-1)^{m+1}\frac{1}{m}=1+\frac{1}{2}+...+\frac{1}{m}$

For $n=m+1$

$\left(\sum\limits_{k=1}^{m}(-1)^{k+1}{m\choose k}\frac{1}{k}\right)+(-1)^{m+2}\frac{1}{m+1}=1+\frac{1}{2}+...+\frac{1}{m+1}$

If $m$ is even, equality is true, but not if $m$ is odd. Is this correct?

Answer 1

We have: $$ \sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1} x^k = 1-(1-x)^n\tag{1}$$ hence: $$ \sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}\frac{1}{k} = \int_{0}^{1}\frac{1-(1-x)^n}{x}\,dx= \int_{0}^{1}\frac{1-x^n}{1-x}\,dx\tag{2}$$ and: $$ \sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}\frac{1}{k} = \int_{0}^{1}\left(1+x+\ldots+x^{n-1}\right)\,dx = 1+\frac{1}{2}+\ldots+\frac{1}{n}=H_n\tag{3}$$ as wanted.

Answer 2

Define $$ f(n)=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\frac1k\tag1 $$ Then, $f(0)=0$ and for $n\gt0$, $$ \begin{align} f(n) &=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\frac1k\tag2\\ &=\sum_{k=1}^n(-1)^{k-1}\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]\frac1k\tag3\\ &=\sum_{k=1}^{n-1}(-1)^{k-1}\binom{n-1}{k}\frac1k+\sum_{k=1}^n(-1)^{k-1}\binom{n-1}{k-1}\frac1k\tag4\\ &=f(n-1)+\frac1n\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\tag5\\ &=f(n-1)+\frac1n\tag6 \end{align} $$ Explanation:
$(3)$: Pascal's Rule
$(4)$: distribute the summation
$(5)$: apply $(1)$ for $n-1$ and $\frac1k\binom{n-1}{k-1}=\frac1n\binom{n}{k}$
$(6)$: $\sum\limits_{k=1}^n(-1)^{k-1}\binom{n}{k}=1$

Therefore, $f(n)$ is the $n^\text{th}$ Harmonic Number for $n\ge0$.