15
$\begingroup$

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.

$\endgroup$
2

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ A very nice proof! $\endgroup$ Jun 3, 2017 at 1:30
16
$\begingroup$

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

$\endgroup$
2
  • 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, 2016 at 16:32
  • 1
    $\begingroup$ This has reminded of my own proof of a similar identity: artofproblemsolving.com/community/q1h352146p1915602 $\endgroup$ May 18, 2016 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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