Prove without induction that $\sum_{r=1}^n {n\choose r}(-1)^{r+1}\frac1r=\sum_{r=1}^n \frac1r$

Question

Prove without induction that $$\sum_{r=1}^n {n\choose r}(-1)^{r+1}\dfrac{1}{r}=\sum_{r=1}^n \dfrac{1}{r}$$ for $n\geq1$.

I have shown the above using induction. However, I am interested in knowing if we can show it directly without using induction.

This is not entirely trivial, I think, if one is armed only with the very basic ideas of combinatorial identities. This can be proved in at least two different ways: one using induction and the other is by evaluating an integral. However, regarding the second approach, I am quite certain that if not known beforehand which integral to compute to get this equality, it is a hard exercise.

EDIT: In the link claiming to be a duplicate of my question, induction was allowed. I am looking for approaches that use no induction or calculus. So this question is different.

Answer 1

Start by

$$\sum_{r=0}^n {n\choose r}x^r=(1+x)^n$$

Which can be converted to integration

$$\sum_{r=1}^n {n\choose r}\frac{(-1)^{r}}{r}=\int^{-1}_0 \frac{(x+1)^n-1}{x} dx$$

By substitution we have

$$\sum_{r=1}^n {n\choose r}\frac{(-1)^{r+1}}{r}=\int^{1}_0 \frac{t^n-1}{t-1} dt = H_n$$

Note the last step by expanding $(1-t)^{-1}$.

Answer 2

Claim:

$$\sum_{r=1}^n {n\choose r}\frac{(-1)^{r+1}}{r}=\sum_{r=1}^n\frac{1}{r}$$

Proof:

• Call the left hand side $f(n)$, then set $F(x)=\sum_{n\ge1}f(n)x^n$. Then:

$$F(x)=\sum_{n\ge1}\sum_{r=1}^n {n\choose r}\frac{(-1)^{r+1}}{r}x^n =\sum_{r\ge1}\sum_{n\ge r} {n\choose r}\frac{(-1)^{r+1}}{r}x^n$$

$$=\sum_{r\ge1} \frac{(-1)^{r+1}}{r}\sum_{n\ge r} {n\choose r}x^n =\sum_{r\ge1} \frac{(-1)^{r+1}}{r}\frac{x^r}{(1-x)^{r+1}} =\frac{-1}{1-x}\sum_{r\ge1}\frac{1}{r}\left(\frac{-x}{1-x}\right)^r$$

$$=\frac{-1}{1-x}\log \frac{1}{1-\frac{-x}{1-x}}=\frac{-1}{1-x}\log(1-x)=\frac{1}{1-x}\log\frac{1}{1-x}$$

• Now, call the right hand side $g(n)$, then set $G(x)=\sum_{n\ge1}g(n)x^n$. Then:

$$G(x)=\sum_{n\ge1}\sum_{r=1}^n\frac{1}{r}x^n=\sum_{r\ge1}\sum_{n\ge r}\frac{1}{r}x^n=\sum_{r\ge1}\frac{1}{r}\sum_{n\ge r}x^n$$

$$=\sum_{r\ge1}\frac{1}{r}\frac{x^r}{1-x}=\frac{1}{1-x}\sum_{r\ge1}\frac{x^r}{r}=\frac{1}{1-x}\log\frac{1}{1-x}$$

• So, $F(x)=G(x)$, hence $f(n)=g(n)$, and we are done.