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

Question

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.

Please help!

Answer 1

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.

Answer 2

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