Proof of a sum with binomial coefficients $\sum_{k=1}^n (-1)^{k+1}{\binom nk}\frac{1}{k} = 1 + \frac{1}{2} + \ldots +\frac{1}{n}$ [duplicate]

I need to prove:

$$\sum_{k=1}^n (-1)^{k+1}{n \choose k}\frac{1}{k} = 1 + \frac{1}{2} + \ldots +\frac{1}{n}$$

for $n \in \mathbb N$

I should use mathematical induction. So, I've tried going simply by inductive steps.

It's true for $n=1$.

But when I try to evaluate the left side of the term by plugging in the values from $1$ to, say, $5$, I get that the series is actually this:

$$1-1+1-1+1-1+1-1+\ldots$$

Which should at the end equal $0$? But in that case, the problem doesn't make any sense.

Also, by assuming that the term is true for $n=k, k>1$, and then trying to prove that it's also true for $n=k+1$, I can't seem to get anything concrete.

• I think the error hides in the reasoning leading to the sum $1-1+1-1\ldots$. Oct 26 '15 at 18:12
• What you are getting on the left-hand side is wrong. Remember, $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ so e.g. $\binom{2}{1}=2$. Then $\binom{2}{1}\frac{1}{1}-\binom{2}{2}\frac{1}{2}=2-\frac{1}{2}=\frac{3}{2}$ $=1+\frac{1}{2}$. Oct 26 '15 at 18:13
• You can see this link: math.stackexchange.com/questions/1490571/… Oct 26 '15 at 18:15
• This is not duplicate in my opinion as the index makes a difference. For a third variant, $\sum_0^n {n \choose k} (-1)^{k+1}\frac{1}{k+1} = 0$. Oct 26 '15 at 18:23

You’ve clearly made some error in reasoning or calculation. For $n=4$, say, it’s

$$\binom41\frac11-\binom42\frac12+\binom43\frac13-\binom44\frac14=4-3+\frac43-\frac14=\frac{25}{12}\;,$$

and

$$1+\frac12+\frac13+\frac14=\frac{12+6+4+3}{12}=\frac{25}{12}\;,$$

just as it’s supposed to be.

In your induction step you should be trying to prove that

$$\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n+1}k\frac1k=\sum_{k=1}^{n+1}\frac1k\tag{1}$$

from the induction hypothesis that

$$\sum_{k=1}^n(-1)^{k+1}\binom{n}k\frac1k=\sum_{k=1}^n\frac1k\;.\tag{2}$$

The most natural way to try to do this is to add $\frac1{n+1}$ to both sides of $(2)$ and then try to reduce the lefthand side to the lefthand side of $(1)$, i.e., to try to show that

$$\sum_{k=1}^n(-1)^{k+1}\binom{n}k\frac1k+\frac1{n+1}=\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n+1}k\frac1k\;.\tag{3}$$

It would certainly help if the binomial coefficients matched up; this suggests that we should use Pascal’s identity on the righthand side of $(3)$:

\begin{align*} \sum_{k=1}^{n+1}(-1)^{k+1}\binom{n+1}k\frac1k&=\sum_{k=1}^{n+1}(-1)^{k+1}\left(\binom{n}k+\binom{n}{k-1}\right)\frac1k\\ &=\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n}k\frac1k+\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n}{k-1}\frac1k\;. \end{align*}

Thus, we’re trying to prove that

$$\sum_{k=1}^n(-1)^{k+1}\binom{n}k\frac1k+\frac1{n+1}=\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n}k\frac1k+\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n}{k-1}\frac1k\;.\tag{4}$$

The first sum on the righthand side of $(4)$ might as well just run from $k=1$ to $n$, since $\binom{n}{n+1}=0$ anyway. Thus, we can subtract that sum from both sides to find that $(4)$ is equivalent to

$$\frac1{n+1}=\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n}{k-1}\frac1k\;.\tag{5}$$

At this point it’s useful to know that

$$\binom{n}{k-1}\frac1k=\binom{n+1}k\frac1{n+1}\;;$$

I’ll leave that to you to verify. Then an easy application of the binomial theorem will get you what you want.

By calculating some integrals, we can prove the equation. Note that in some step, there is a change of variable of the the form $y=1-x$ and then renaming $y$ to $x$. $$\sum_{k=1}^n(-1)^{k+1}{n \choose k}\frac1k=\\ \sum_{k=1}^n(-1)^{k-1}{n \choose k}\int_0^1x^{k-1}dx=\\ \int_0^1\sum_{k=1}^n{n \choose k}(-x)^{k-1}dx=\\ \int_0^1\frac{(1-x)^n-1}{-x}dx=\\ \int_0^1\frac{x^n-1}{x-1}dx=\\ \int_0^1\sum_{k=1}^nx^{k-1}dx=\\ \sum_{k=1}^n\left[\frac{x^k}k\right]_{x=0}^1=\\ \sum_{k=1}^n\frac1k$$