Summing $\sum_{k=1}^n \binom{2n-2k}{n-k}\frac{H_{2k} - 2H_{k}}{2n-2k-1} \binom{2k}{k}$

Question

The sum in the question has a nice closed-form: $$ \sum_{k = 1}^{n}\binom{2n - 2k}{n - k} \frac{H_{2k} - 2H_{k}}{2n-2k-1}\binom{2k}{k} = \frac{1}{n}\left[4^{n} - 3\binom{2n-1}{n}\right],$$ where $H_k$ is the harmonic number $H_n = \sum_{k=1}^n 1/k.$

My proof is excruciating:

• It involved the specialization of a two-variable generating function ( $x$ and $y$ take different functions of $t$ ) so that I could use an identity that seems to have no mere mortal-constructed proof ( a variant of the WZ method was used, I believe ).
• In the process of the proof, I noticed that the expression in big parentheses on the RHS is a sequence of integers, and I searched the OEIS to find $A213119$.
• As logarithms are involved, it was a matter of talking the arguments into the logarithm to find that my generating function was indeed equal to implied by the right hand side of the equation.

I seek a simpler, more direct proof.

A contributor wanted to know where the identity originated. It originated as an attempt to prove the very pretty

$$ \sum_{k = 1}^{n}\binom{n}{k}^{2}H_{k} = \binom{2n}{n}\left(\,{2H_{n} - H_{2n}}\,\right) $$

It may be impossible not to use this in any attempted proof, but hopefully, the specialization of a two-variable generating function can be avoided.

Answer 1

With the following I present a proof to show that it can be done and perhaps inspire additional efforts at further simplification. A combinatorial proof would be quite nice.

We seek to verify the identity

$$\sum_{k=1}^n {2n-2k\choose n-k} \frac{H_{2k} - 2H_k}{2n-2k-1} {2k\choose k} = \frac{1}{n} \left[4^n - 3 {2n-1\choose n}\right].$$

Preliminary. We get for the first piece in $H_{2k}$ call it $A$ that

$$\sum_{k=1}^n {2n-2k\choose n-k} \frac{1}{2n-2k-1} {2k\choose k} [z^{2k}] \frac{1}{1-z} \log\frac{1}{1-z} \\ = \sum_{k=0}^{n-1} {2k\choose k} \frac{1}{2k-1} {2n-2k\choose n-k} [z^{2n-2k}] \frac{1}{1-z} \log\frac{1}{1-z}$$

We may raise $k$ to $n$ because the function in $z$ has no constant term:

$$[z^{2n}] \frac{1}{1-z} \log\frac{1}{1-z} \sum_{k=0}^{n} {2k\choose k} \frac{1}{2k-1} {2n-2k\choose n-k} z^{2k}$$

Now the coefficient extractor enforces the upper limit of the sum and we get (in fact expansions start at $z^{2k+1}$ which cancels $k=n$ already)

$$[z^{2n}] \frac{1}{1-z} \log\frac{1}{1-z} \sum_{k\ge 0} {2k\choose k} \frac{1}{2k-1} {2n-2k\choose n-k} z^{2k} \\ = - [z^{2n}] \frac{1}{1-z} \log\frac{1}{1-z} [w^n] \sqrt{1-4wz^2} \frac{1}{\sqrt{1-4w}}.$$

The same method yields for the second piece in $H_k$ call it $B$

$$- [z^{n}] \frac{1}{1-z} \log\frac{1}{1-z} [w^n] \sqrt{1-4wz} \frac{1}{\sqrt{1-4w}}.$$

First part. Continuing with piece $B$

$$[w^n] \sqrt{1+\frac{4w(1-z)}{1-4w}} = - [w^n] \sum_{k\ge 0} {2k\choose k} \frac{1}{2k-1} (-1)^k \frac{w^k (1-z)^k}{(1-4w)^k} \\ = - \sum_{k=0}^n {2k\choose k} \frac{1}{2k-1} (-1)^k [w^{n-k}] \frac{(1-z)^k}{(1-4w)^k} \\ = - 4^n \sum_{k=0}^n {2k\choose k} \frac{1}{2k-1} (-1)^k (1-z)^k 4^{-k} {n-1\choose k-1}$$

and extracting the coefficient in $[z^n]$

$$4^n \sum_{k=1}^n {2k\choose k} \frac{1}{2k-1} (-1)^k 4^{-k} {n-1\choose k-1} [z^n] (1-z)^{k-1} \log\frac{1}{1-z} \\ = 4^n \sum_{k=1}^n {2k\choose k} \frac{1}{2k-1} (-1)^k 4^{-k} {n-1\choose k-1} \sum_{q=0}^{k-1} (-1)^q {k-1\choose q} \frac{1}{n-q}.$$

Now

$${n-1\choose k-1} {k-1\choose q} = \frac{(n-1)!}{(n-k)!\times q! \times (k-1-q)!} = {n-1\choose q} {n-1-q\choose k-1-q}$$

Switching the order of the summation,

$$4^n \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-1)^q}{n-q} \sum_{k=q+1}^n {n-1-q\choose k-1-q} {2k\choose k} \frac{1}{2k-1} (-1)^k 4^{-k} \\ = \frac{4^n}{n} \sum_{q=0}^{n-1} {n\choose q} (-1)^q \sum_{k=q+1}^n {n-1-q\choose k-1-q} {2k\choose k} \frac{1}{2k-1} (-1)^k 4^{-k} \\ = - \frac{4^n}{n} \sum_{q=0}^{n-1} {n\choose q} (-1)^q \sum_{k=q+1}^n {n-1-q\choose k-1-q} [z^k] \sqrt{1+z}.$$

The inner sum is

$$\sum_{k=0}^{n-1-q} {n-1-q\choose k} [z^{k+q+1}] \sqrt{1+z} = \sum_{k=0}^{n-1-q} {n-1-q\choose k} [z^{n-k}] \sqrt{1+z} \\ = [z^n] \sqrt{1+z} \sum_{k=0}^{n-1-q} {n-1-q\choose k} z^k = [z^n] \sqrt{1+z} (1+z)^{n-1-q}.$$

Substitute into the outer sum to get

$$- \frac{4^n}{n} [z^n] \sqrt{1+z} \sum_{q=0}^{n-1} {n\choose q} (-1)^q (1+z)^{n-1-q} = - \frac{4^n}{n} [z^n] \frac{1}{\sqrt{1+z}} (- (-1)^n + z^n) \\ = - \frac{4^n}{n} \left(- 4^{-n} {2n\choose n} + 1\right) = - \frac{4^n}{n} + {2n\choose n} \frac{1}{n}.$$

Second part. Here we may recycle the first segment from the easy piece $B$ and obtain for piece $A$

$$4^n \sum_{k=1}^n {2k\choose k} \frac{1}{2k-1} (-1)^k 4^{-k} {n-1\choose k-1} [z^{2n}] (1-z^2)^{k-1} (1+z) \log\frac{1}{1-z}.$$

The coefficient extractor in $z$ has two parts, the first of which is

$$\sum_{q=0}^{k-1} (-1)^q {k-1\choose q} \frac{1}{2n-2q}$$

which contributes half the value of the piece $B.$ The second is

$$\sum_{q=0}^{k-1} (-1)^q {k-1\choose q} \frac{1}{2n-1-2q}.$$

This yields

$$-4^n [z^n] \sqrt{1+z} \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-1)^q}{2n-1-2q} (1+z)^{n-1-q} \\ = -4^n [z^n] \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-1)^q}{2n-1-2q} (1+z)^{n-1/2-q} \\ = -4^n \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-1)^q}{2n-1-2q} (n-1/2-q)^{\underline{n}}/n!.$$

We have for the falling factorial

$$ \prod_{p=0}^{n-1} (n-1/2-q-p) = \frac{1}{2^n} \prod_{p=0}^{n-1} (2n-1-2q-2p) \\ = \frac{1}{2^n} \prod_{p=-(n-1)}^0 (1-2q-2p) = \frac{(-1)^n}{2^n} \prod_{p=q-(n-1)}^{q} (2p-1) \\ = \frac{(-1)^{n+1}}{2^n} \frac{(2q-1)!}{2^{q-1} (q-1)!} \prod_{p=q-(n-1)}^{-1} (2p-1).$$

With $2q-2(n-1)-1 = 2q-2n+1$ this finally becomes

$$\frac{(-1)^{q}}{2^n} \frac{(2q-1)!}{2^{q-1} (q-1)!} \frac{(2n-1-2q)!}{2^{n-1-q} (n-1-q)!} \\ = \frac{(-1)^{q}}{2^{2n-1}} \frac{(2q)!}{q!} \frac{(2n-1-2q)!}{(n-1-q)!}.$$

This was for $1\le q\le n-1.$ We get for $q=0$

$$\frac{1}{2^n} \prod_{p=-(n-1)}^0 (1-2p) = \frac{1}{2^n} \frac{(2n-1)!}{2^{n-1} (n-1)!}$$

and we see that the generic term in four factorials represents this case correctly as well.

Returning to the sum we obtain

$$-\frac{2}{n} \sum_{q=0}^{n-1} {2q\choose q} {2n-2-2q\choose n-1-q} \\ = -\frac{2}{n} [z^{n-1}] \frac{1}{\sqrt{1-4z}} \frac{1}{\sqrt{1-4z}} = -\frac{2}{n} [z^{n-1}] \frac{1}{1-4z} = -\frac{2}{n} 4^{n-1} = -\frac{1}{2} \frac{4^n}{n}.$$

Conclusion. We now collect the three pieces with $A$ first then $B:$

$$-\frac{1}{2} \frac{4^n}{n} - \frac{1}{2} \frac{4^n}{n} + \frac{1}{2} \frac{1}{n} {2n\choose n} \\ + 2 \frac{4^n}{n} - 2 \frac{1}{n} {2n\choose n} = \frac{4^n}{n} - \frac{3}{2} \frac{1}{n} {2n\choose n} = \frac{4^n}{n} - 3 \frac{1}{n} {2n-1\choose n-1}.$$

This is indeed

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n} \left[4^n - 3 {2n-1\choose n}\right].}$$

Answer 2

Here is another variation.

We observe the left-hand side of OPs identity is the coefficient of a Cauchy-product of series and we start with separating the factors. We obtain \begin{align*} \color{blue}{\sum_{n=1}^{\infty}}&\color{blue}{\left(\sum_{k=1}^n\binom{2n-2k}{n-k}\frac{H_{2k}-H_k}{2n-2k-1}\binom{2k}{k}\right)z^n}\\ &=\left(\sum_{m=1}^\infty\binom{2m}{m}\left(H_{2m}-2H_m\right)z^m\right) \left(\sum_{l=0}^\infty\binom{2l}{l}\frac{1}{2l-1}z^l\right)\tag{1} \end{align*}

We will make use from the generating functions of the central binomial coefficients and of the closely related Catalan numbers. \begin{align*} \sum_{n=0}^\infty\binom{2n}{n}z^n&=\frac{1}{\sqrt{1-4z}}\\ C(z)=\sum_{n=0}^\infty\binom{2n}{n}\frac{1}{n+1}z^n&=\frac{1-\sqrt{1-4z}}{2z}=\frac{2}{1+\sqrt{1-4z}}\tag{2} \end{align*}

We start with the easy part of (1) and consider the right-hand series. We obtain \begin{align*} \color{blue}{\sum_{l=0}^\infty}\color{blue}{\binom{2l}{l}\frac{1}{2l-1}z^{l}} &=-1+2z\sum_{l=1}^\infty\binom{2l-1}{l-1}\frac{1}{2l-1}z^{l-1}\tag{3}\\ &=-1+2z\sum_{l=0}^\infty\binom{2l}{l}\frac{1}{l+1}z^l\tag{4}\\ &=-1+2z\left(\frac{1-\sqrt{1-4z}}{2z}\right)\tag{5}\\ &\,\,\color{blue}{=-\sqrt{1-4z}}\tag{6} \end{align*} and observe we have in (5) the generating function $C(z)$ of the Catalan numbers in disguise.

Comment:

• In (3) we separate the first term and use $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (4) we use $\binom{p}{q}=\binom{p}{p-q}$ and shift the index to start with $l=0$.

• In (5) we use $C(z)$ and simplify afterwards.

This was the warm-up section. Now we consider the left-hand series of (1). But prior to this we recall a nice polynomial identity in the following intermezzo.

Intermezzo: We introduce generalised harmonic numbers $H_n(x)=\sum_{j=1}^n\frac{1}{j+x}$ and consider the following polynomial in $x$ and $n,k$ non-negative integers: \begin{align*} \frac{d}{dx}\binom{n+x}{k}&=\frac{1}{k!}\frac{d}{dx}\prod_{j=0}^{k-1}(n+x-j)\\ &=\frac{1}{k!}\sum_{l=0}^{k-1}\prod_{{j=0}\atop{j\ne l}}^{k-1}(n+x-j)\\ &=\binom{n+x}{k}\sum_{l=0}^{k-1}\frac{1}{n+x-l}\\ &=\binom{n+x}{k}\left(H_n(x)-H_{n-k}(x)\right)\tag{7}\\ \end{align*} Evaluating the identity (7) at $x=0$ results in \begin{align*} \left.\left(\frac{d}{dx}\binom{n+x}{k}\right)\right|_{x=0}=\binom{n}{k}\left(H_n-H_{n-k}\right)\tag{8} \end{align*}

Now we are ready to tackle the left-hand series of (1). We obtain \begin{align*} \color{blue}{\sum_{m=1}^\infty}&\color{blue}{\binom{2m}{m}\left(H_{2m}-2H_m\right)z^m}\\ &=\sum_{m=1}^\infty\binom{2m}{m}\left(H_{2m}-H_m\right)z^m-\sum_{m=1}^\infty\binom{2m}{m}H_mz^m\\ &=\left.\left(\frac{d}{dx}\left(\sum_{m=1}^\infty\binom{2m+x}{m}z^m\right)\right)\right|_{x=0} -\sum_{m=1}^\infty\binom{2m}{m}H_mz^n\tag{9}\\ &=\left.\left(\frac{d}{dx}\left(\frac{1}{\sqrt{1-4z}}\left(\frac{1-\sqrt{1-4z}}{2z}\right)^x\right)\right)\right|_{x=0} -\sum_{m=1}^\infty\binom{2m}{m}H_mz^n\tag{10}\\ &=\frac{1}{\sqrt{1-4z}}\left.\left(\frac{d}{dx}\left(C(z)\right)^x\right)\right|_{x=0} -\sum_{m=1}^\infty\binom{2m}{m}H_mz^n\\ &=\frac{1}{\sqrt{1-4z}}\left.\left(\left(C(z)\right)^x\ln C(z)\right)\right|_{x=0} -\sum_{m=1}^\infty\binom{2m}{m}H_mz^n\tag{11}\\ &=\frac{1}{\sqrt{1-4z}}\ln C(z)-\frac{2}{\sqrt{1-4z}}\ln\left(\frac{1+\sqrt{1-4z}}{2\sqrt{1-4z}}\right)\tag{12}\\ &=\frac{1}{\sqrt{1-4z}}\ln C(z)+\frac{2}{\sqrt{1-4z}}\ln\left(C(z)\sqrt{1-4z}\right)\\ &\,\,\color{blue}{=\frac{1}{\sqrt{1-4z}}\left(3\ln C(z)+2\ln\sqrt{1-4z}\right)}\tag{13} \end{align*}

Comment:

• In (9) we apply the identity (8) from the intermezzo.

• In (10) we use a generalised generating function of the central binomial coefficients. A derivation of it can be found for instance at this MSE post.

• In (11) we make the derivation.

• In (12) we use the identity (9) stated in this paper by H. Chen, which is certainly a formidable source to derive many different variations of proofs of the current problem. We do some simplifications in the following lines.

Putting (13) and (6) in (1) we obtain \begin{align*} \color{blue}{\sum_{n=1}^{\infty}}&\color{blue}{\left(\sum_{k=1}^n\binom{2n-2k}{n-k}\frac{H_{2k}-H_k}{2n-2k-1}\binom{2k}{k}\right)z^n}\\ &=\left(\sum_{m=1}^\infty\binom{2m}{m}\left(H_{2m}-2H_m\right)z^m\right) \left(\sum_{l=0}^\infty\binom{2l}{l}\frac{1}{2l-1}z^l\right)\\ &=\left(\frac{1}{\sqrt{1-4z}}\left(3\ln C(z)+2\ln\sqrt{1-4z}\right)\right)\left(-\sqrt{1-4z}\right)\\ &\,\,\color{blue}{=\ln\frac{1}{1-4z}-3\ln C(z)}\tag{14} \end{align*}

Finally we calculate the generating functions from the right hand side of OP's identity.

We obtain \begin{align*} \color{blue}{\sum_{n=1}^\infty}&\color{blue}{\frac{1}{n}\left(4^n-3\binom{2n-1}{n}\right)z^n}\\ &=\sum_{n=1}^\infty\frac{1}{n}\left(4z\right)^n+\sum_{n=1}^\infty\binom{2n-1}{n-1}\frac{1}{n}z^n\\ &=\ln\frac{1}{1-4z}-\frac{3}{2}\sum_{n=1}^\infty\binom{2n}{n}\frac{1}{n}z^n\\ &\,\,\color{blue}{=\ln\frac{1}{1-4z}-3\ln C(z)}\tag{15} \end{align*} in accordance with (14) and the claim follows.

The term $\ln C(z)$ in (15) follows from (2) by division by $z$ and integrating both sides of the generating function of the central binomial coefficients. Note, this is also stated in Chen's paper shortly after corollary 4.