# A combinatorial identity involving harmonic numbers

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$.
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$.
• 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$$ – esg May 17 '16 at 16:32