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:


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!

  • $\begingroup$ I think the error hides in the reasoning leading to the sum $1-1+1-1\ldots$. $\endgroup$ Oct 26 '15 at 18:12
  • $\begingroup$ 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}$. $\endgroup$
    – Sean Clark
    Oct 26 '15 at 18:13
  • $\begingroup$ You can see this link: math.stackexchange.com/questions/1490571/… $\endgroup$
    – Nate River
    Oct 26 '15 at 18:15
  • $\begingroup$ 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$. $\endgroup$
    – Weaam
    Oct 26 '15 at 18:23

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




just as it’s supposed to be.

In your induction step you should be trying to prove that


from the induction hypothesis that


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


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


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


At this point it’s useful to know that


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


Not the answer you're looking for? Browse other questions tagged or ask your own question.