A combinatorial identity involving harmonic numbers

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


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.