The harmonic numbers are given by $$H_n=\sum_{k=1}^n\frac{1}{k}.$$ Numerical calculation suggests $$ \sum_{k=1}^{n}(-1)^k{n\choose k}{n+k\choose k}\sum_{i=1}^{k}\frac{1}{n+i}=(-1)^nH_n. $$ I can not give a proof of this identity. How to prove it?

Hints, references or proof are all welcome.


First we prove the formula $$\sum_{k=0}^n (-1)^k\binom{n}{k}\binom {x+k}{k} = (-1)^n\binom xn,\tag{1}$$ which is special case of Vandermonde's theorem: $$\begin{aligned} \sum_{k=0}^n (-1)^k\binom{n}{k}\binom {x+k}{k} &= \sum_{k=0}^n \binom n{n-k} \binom{-x-1}{k}\\ &= \binom{n-x-1}{n} = (-1)^n\binom xn. \end{aligned}$$ Since $(1)$ is an identity of polynomials in $x$, we may differentiate it with respect to $x$, obtaining $$\sum_{k=0}^n (-1)^k\binom{n}{k}\binom {x+k}{k}\sum_{i=1}^k\frac{1}{x+i} =(-1)^n\binom xn \sum_{i=0}^{n-1}\frac{1}{x-i}. $$ The OP's identity follows on setting $x=n$.

The same method can be used to prove many identities involving harmonic numbers.

  • $\begingroup$ A very nice proof! $\endgroup$ – Ji-Cai Liu Jun 3 '17 at 1:30

Here is a proof.

At first, use $(-1)^k\binom{n+k}k=\binom{-n-1}k$. Then $$F(y):=\sum_k (-1)^k\binom{n}k\binom{n+k}ky^k=[x^n] (1+x)^n(1+xy)^{-n-1}.$$ Next, for any polynomial $F(y)=\sum c_ky^k$ we have $$ \sum c_k\sum_{i=1}^k\frac1{n+i}=\int_0^1 y^n\frac{F(y)-F(1)}{y-1}dy. $$ Integration over $[0,1]$ and taking the coefficient of $x^n$ commute, thus we have to prove $$ [x^n]\int_0^1\frac{y^n\left((\frac{x+1}{1+xy})^n\cdot \frac1{1+xy}-\frac1{1+x}\right)}{y-1}dy=(-1)^nH_n. $$ Idea is to make for a first summand a change of variables $t=y(x+1)/(1+xy)$, this $t$ also varies from 0 to 1. We can not deal with summands separetely on $[0,1]$, since integrals diverge in 1. Thus we should replace $\int_0^1$ to $\int_0^Y$ and after that let $Y$ tend to $1-0$. Denote by $T=Y(x+1)/(1+xY)$ the corresponding upper limit after our change of variables. Straightworfard computations show $$ \int_0^Y\frac{y^n(\frac{x+1}{1+xy})^n}{(y-1)(1+xy)}dy=\int_0^T\frac{t^n}{(t-1)(x+1)}dt. $$ Now we realize that changing $t$ to $y$ makes two integrands the same. So, $$ \int_0^Y\frac{y^n\left((\frac{x+1}{1+xy})^n\cdot \frac1{1+xy}-\frac1{1+x}\right)}{y-1}dy=\int_Y^T\frac{y^n}{(y-1)(x+1)}dy=\\ \int_Y^T\frac{y^n-1}{(y-1)(x+1)}dy+\frac1{x+1}\log\frac{1-T}{1-Y}. $$ First guy tends to 0 when $Y$ and $T$ approach 1. The second tends to $\frac{-1}{x+1}\log(1+x)$. It remains to note that indeed $[x^n]\frac{-1}{x+1}\log(1+x)=(-1)^n H_n$.

  • 7
    $\begingroup$ The following variant of the proof may be simpler: the relation $F(y)=[x^n] \frac{1}{1+x}\frac{1}{(1-\frac{x}{1+x}(1-y))^{n+1}}$ shows that $F(y)=(-1)^n F(1-y)$. Thus $F(1)-F(y)=(-1)^n \sum_{k=1}^n { n\choose k} { n+k \choose k} (-1)^{k+1} (1-y)^{k}$ and (using the Beta-integral $\int_0^1 (1-y)^{k-1} y^n\,dy=\frac{(k-1)!\,n!}{(n+k)!}$) $$\int_0^1 \frac{1 -F(y)}{1-y}\,y^n\,dy=(-1)^n \sum_{k=1}^n{n \choose k}\frac{(-1)^{k+1}}{k}=(-1)^n\,H_n$$ $\endgroup$ – esg May 17 '16 at 16:32
  • 1
    $\begingroup$ This has reminded of my own proof of a similar identity: artofproblemsolving.com/community/q1h352146p1915602 $\endgroup$ – Max Alekseyev May 18 '16 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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