# Proof for any positive integer n the following equality hold [duplicate]

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

## 2 Answers

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

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