Harmonic series and the binomial theorem

Question

I recently came across the following identity relating to the harmonic series: $\displaystyle \sum_{r=1}^{n}\frac{(-1)^{r+1}C_r^{n}}{r} =\sum_{r=1}^{n}\frac{1}{r}$. It was the first time I had seen this identity, and it got me thinking: are there any more interesting results relating to the sum $\displaystyle \sum_{r=1}^{n}\frac{(-1)^{r+1}C_r^{n}}{r}$ that we can deduce from this relationship? One that is pretty immediate is the fact that this sum must diverge, but I'd be interested to see if anyone could come up with some less-obvious or creative ones.

Answer 1

For integer $n$ and real $x \not\in \{-n, -n+1, \ldots, -1, 0\}$ $$ \sum_r \frac{ (-1)^r }{x+r}\binom{n}{r} = \frac{1}{x} \frac{1}{\binom{n+x}{n}} $$ where the sum over $r$ will be a finite sum if $n$ is an integer. This looks like your identity, but includes the $r=0$ term which yours, of course, does not.

Answer 2

Remark : the exact identity is $\sum_{r=1}^n \frac{(-1)^{\mathbf{r-1}}\binom nr}{r} = \sum_{r=1}^n \frac 1r$.

One way to prove this identity is induction.

Another way is as follows :

• start with $f:x\mapsto \sum_{r=1}^n \binom nr\frac{(-1)^{r-1}x^r}{r}$;
• $f$ being a polynomial function is differentiable with $f'(x)=\sum_{r=1}^n \binom nr x^{r-1} = \frac1x \left[1-(1-x)^n\right]$ (prolongated with $f'(0)=n$).
• so $f(x)=f(0)+\int_0^x f'(t){\rm d}t$. Let's do that computation : \begin{align}f(x)&=\int_0^x \frac{1-(1-t)^n}{t}{\rm d}t \\ &\underset{u=1-t}{=} -\int_1^{1-x} \frac{1-u^n}{1-u}{\rm d}u \\ &= -\int_1^{1-x}(1+u+u^2+\dots+u^{n-1}){\rm d}u \\ &= -\left[u+\frac{u^2}{2}+\dots+\frac{u^n}{n}\right]_1^{1-x} \\ &= (1+\frac12+\dots+\frac1n)-((1-x)+\frac{(1-x)^2}{2}+\dots + \frac{(1-x)^n}{n}) \end{align}
• the value $f(1)$ gives the identity.

I think this technique can be generalized, and that it could prove a more general formula obtained by replacing $\frac{x^r}{r}$ by $\frac{x^{r+\alpha}}{r+\alpha}$ in the definition of function $f$...

Answer 3

The identity has a probabilistic proof. This is based on https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

Consider the following question:

There are $n$ types of coupons. Draw one coupon at a time, independence is assumed. The type $i$ is obtained with a probability of $p_i$ so that $\sum_{i=1}^n p_i=1$. What is the expected number of coupons to collect all types?

Let $T_i$ be the number of draws to collect type $i$. Then we find $E[\max T_i]$. By the inclusion-exclusion principle, $$ \max\{T_1, \ldots,T_n\} = \sum_i T_i -\sum_{i<j}\min\{T_i, T_j\} + \sum_{i<j<k}\min\{T_i, T_j, T_k\}- \ldots + (-1)^{n+1}\min\{T_1,\dots, T_n\}. $$ Taking expected values and noting that $\min \{ T_i, T_j, \ldots \}$ is geometrically distributed, we obtain $$ E[\max T_i]=\sum \frac1{p_i}-\sum_{i<j} \frac1{p_i+p_j}+\sum_{i<j<k}\frac1{p_i+p_j+p_k}-\ldots+(-1)^{n+1}\frac1{p_1+\cdots + p_n}. $$ The above can be written as $$ \int_0^{\infty}\left(1-\prod_{i=1}^n\left(1-e^{-p_i x}\right)\right)dx. $$ In case $p_i=1/n$ for each $i$, we have $$ \int_0^{\infty}\left(1-(1-e^{-\frac xn})^n\right) dx=n\sum_{k=1}^n(-1)^{k+1}\binom nk \frac1k. $$

On the other hand, this expected number can be obtained by using $\max T_i = t_1+\cdots +t_n$ where $t_i$ is the time until $i$th distinct type is obtained given that $i-1$ distinct types are already obtained. Then each $t_i$ is geometrically distributed with parameter $(n-i+1)/n$. Thus, $$ E[\max T_i]=E[t_1]+\cdots + E[t_n]= n\sum_{i=1}^n \frac1{n-i+1}=n\sum_{j=1}^n \frac1j. $$ Hence, $$ n\sum_{k=1}^n(-1)^{k+1}\binom nk \frac1k=n\sum_{j=1}^n \frac1j $$ and the desired equality $$ \sum_{k=1}^n(-1)^{k+1}\binom nk \frac1k=\sum_{j=1}^n \frac1j $$ follows.