# Hard combinatorial identity: $\sum_{l=0}^p(-1)^l\binom{2l}{l}\binom{k}{p-l}\binom{2k+2l-2p}{k+l-p}^{-1}=4^p\binom{k-1}{p}\binom{2k}{k}^{-1}$

Does anyone have idea to prove that? $$\sum_{\ell=0}^{p}(-1)^{\ell}\dfrac{\binom{2\ell}{\ell}\binom{k}{p-\ell}}{\binom{2k+2\ell-2p}{k+\ell-p}} = \dfrac{4^p\binom{k-1}{p}}{\binom{2k}{k}}$$ is true for all $k \in \mathbb{N}, p \in \mathbb{N} \cup \{0\}$. We use the convention that, if $p>k-1$, then $\binom{k-1}{p}=0$

• Have you tried writing the central binomial coefficients in terms of $\binom{\cdot}{1/2}$ and exploiting Vandermonde's identity? – Jack D'Aurizio Jan 13 '18 at 15:06
• I saw in internet that there is a generalization of vandermonde's identity like fonction gamma and fonction hypergéométrique. But I'm not sure what do you mean "in terms of $\binom {\cdot}{1/2}$". Can you precise more? I haven't learned these. – 曾靖國 Jan 13 '18 at 16:07
• Since $$\frac{1}{\sqrt{1-x}}=\sum_{n\geq 0}\frac{\binom{2n}{n}}{4^n}x^n$$ you have $$\binom{2n}{n} = 4^n\binom{n}{-1/2}$$ – Jack D'Aurizio Jan 13 '18 at 16:30
• @JackD'Aurizio: actually it is $\binom{2n}{n} = 4^n\binom{n-1/2}{n}$ – G Cab Jan 13 '18 at 17:38

We obtain \begin{align*} \color{blue}{\sum_{l=0}^p}&\color{blue}{(-1)^l\binom{2l}{l}\binom{k}{p-l}\binom{2k+2l-2p}{k+l-p}^{-1}}\\ &=\sum_{l=0}^p(-1)^{p-l}\binom{2p-2l}{p-l}\binom{k}{l}\binom{2k-2l}{k-l}^{-1}\tag{1}\\ &=4^{p-k}\sum_{l=0}^p\binom{-\frac{1}{2}}{p-l}\binom{k}{l}\binom{k-l-\frac{1}{2}}{k-l}^{-1}\tag{2}\\ &=4^{p-k}\binom{k-\frac{1}{2}}{k}^{-1}\sum_{l=0}^p\binom{-\frac{1}{2}}{p-l}\binom{k-\frac{1}{2}}{l}\tag{3}\\ &=4^{p-k}\binom{k-\frac{1}{2}}{k}^{-1}\binom{k-1}{p}\tag{4}\\ &\color{blue}{=4^p\binom{k-1}{p}\binom{2k}{k}^{-1}}\tag{5} \end{align*} and the claim follows.

Comment:

• In (1) we change the order of summation $l\rightarrow p-l$.

• In (2) we use the binomial identities $$(-4)^n\binom{-\frac{1}{2}}{n}=\color{green}{\binom{2n}{n}}= 4^n\binom{n-\frac{1}{2}}{n}$$

• In (3) we use the binomial identity (the essence) \begin{align*} \binom{k-\frac{1}{2}}{l}\binom{k-\frac{1}{2}}{k}^{-1} &=\frac{\left(k-\frac{1}{2}\right)^{\underline{l}}}{l!} \cdot\frac{k!}{\left(k-\frac{1}{2}\right)^{\underline{k}}}\\ &=\frac{k!}{l!}\cdot\frac{1}{\left(k-l-\frac{1}{2}\right)^{\underline{k-l}}}\\ &=\frac{k!}{l!(k-l)!}\cdot\frac{(k-l)!}{\left(k-l-\frac{1}{2}\right)^{\underline{k-l}}}\\ &=\binom{k}{l}\binom{k-l-\frac{1}{2}}{k-l}^{-1}\\ \end{align*} with $n^{\underline{k}}=n(n-1)\cdots(n-k+1)$ the falling factorial.

• In (4) we apply the Chu-Vandermonde identity.

• In (5) we use the first identity stated in (2).

• Very nice. (+1). I hope this insightful answer will persist. – Marko Riedel Jan 15 '18 at 21:10
• @MarkoRiedel: Many thanks for your nice comment, Marko. Btw. you inspired me to provide this post. – Markus Scheuer Jan 15 '18 at 21:11
• Thank you for the pointer and the credit, I had not seen it. I have not had the time to review it step by step but it really looks like a remarkable generalization. What you have discovered here is an identity by Gosper. Upvoted. The sum-of-residues rule combined with Leibniz yield a powerful method. – Marko Riedel Jan 16 '18 at 0:27

Let's adopt the definition of the Binomial coefficient through the Falling Factorial.

$$\left( \matrix{ r \cr m \cr} \right) = \left\{ {\matrix{ {{{r^{\,\underline {\,m\,} } } \over {m!}}} & {\left| {\;0 \le m \in \mathbb Z} \right.} \cr 0 & {\left| {\;\neg \left( {0 \le m \in \mathbb Z} \right)} \right.} \cr } } \right.$$ with $r$ real or even complex.

Now, the binomial coefficient at the denominator of the sum shall be not null, that is it shall be $0 \le k-p$ with the above definition. So let's put $m=k-p$ and rewite the proposed identity as $$\bbox[lightyellow] { \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,p} \right)} {\left( { - 1} \right)^{\,l} {{\left( \matrix{ 2l \cr l \cr} \right)\left( \matrix{ m + p \cr p - l \cr} \right)} \over {\left( \matrix{ 2l + 2m \cr m + l \cr} \right)}}} = 4^{\,p} {{\left( \matrix{ m + p - 1 \cr p \cr} \right)} \over {\left( \matrix{ 2m + 2p \cr m + p \cr} \right)}}\quad \left| {\;0 \le m,p \in \mathbb Z} \right. } \tag{1}$$ Note that the bounds of the sum can be omitted since they are implicit in the binomials.

With the adopted definition, the central binomial can be written as $$\left( \matrix{ 2n \cr n \cr} \right) = 2^{\,2\,n} \left( \matrix{ n - 1/2 \cr n \cr} \right) = \left( { - 1} \right)^{\,n} 2^{\,2\,n} \left( \matrix{ - 1/2 \cr n \cr} \right) = \left( { - 4} \right)^{\,n} \left( \matrix{ - 1/2 \cr n \cr} \right)$$

Let's then remind that, for the Rising and Falling Factorial we have \eqalign{ & 1 = x^{\,\underline {\,0\,} } = x^{\,\underline {\,m\,} } \left( {x - m} \right)^{\,\underline {\, - m\,} } \cr & \left( {x + 1} \right)^{\,\overline {\, - m\,} } = \left( {x - m} \right)^{\,\underline {\, - m\,} } = {1 \over {x^{\,\underline {\,m\,} } }}\quad x^{\,\underline {\, - m\,} } = {1 \over {\left( {x + m} \right)^{\,\underline {\,m\,} } }} = {1 \over {\left( {x + 1} \right)^{\,\overline {\,m\,} } }} \cr}

That premised, the summands at the LHS can be written as \bbox[lightyellow] { \eqalign{ & \left( { - 1} \right)^{\,l} {{\left( \matrix{ 2l \cr l \cr} \right)\left( \matrix{ m + p \cr p - l \cr} \right)} \over {\left( \matrix{ 2l + 2m \cr m + l \cr} \right)}} = {{4^{\,l} \left( \matrix{ - 1/2 \cr l \cr} \right)\left( \matrix{ m + p \cr m + l \cr} \right)} \over {4^{\,m + l} \left( \matrix{ m + l - 1/2 \cr m + l \cr} \right)}} = \cr & = {1 \over {4^{\,m} l!}}{{\left( { - 1/2} \right)^{\,\underline {\,l\,} } \left( {m + p} \right)^{\,\underline {\,m + l\,} } } \over {\left( {m + l - 1/2} \right)^{\,\underline {\,m + l\,} } }} \cr} } \tag{2}

And we can rewrite the RHS as \bbox[lightyellow] { \eqalign{ & RHS = 4^{\,p} {{\left( \matrix{ m + p - 1 \cr p \cr} \right)} \over {\left( \matrix{ 2m + 2p \cr m + p \cr} \right)}} = 4^{\,p} {{\left( \matrix{ m + p - 1 \cr p \cr} \right)} \over {4^{\,m + p} \left( \matrix{ m + p - 1/2 \cr m + p \cr} \right)}} = \cr & = {1 \over {4^{\,m} }}{{\sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,p} \right)} {\left( \matrix{ - 1/2 \cr l \cr} \right)\left( \matrix{ m + p - 1/2 \cr p - l \cr} \right)} } \over {\left( \matrix{ m + p - 1/2 \cr m + p \cr} \right)}} \cr} } \tag{3}

and we can demonstrate that each summand on the left corresponds to a summand on the right \bbox[lightyellow] { \eqalign{ & {1 \over {4^{\,m} l!}}{{\left( { - 1/2} \right)^{\,\underline {\,l\,} } \left( {m + p} \right)^{\,\underline {\,m + l\,} } } \over {\left( {m + l - 1/2} \right)^{\,\underline {\,m + l\,} } }} = {1 \over {4^{\,m} }}{{\left( \matrix{ - 1/2 \cr l \cr} \right)\left( \matrix{ m + p - 1/2 \cr p - l \cr} \right)} \over {\left( \matrix{ m + p - 1/2 \cr m + p \cr} \right)}} \cr & \quad \quad \Downarrow \cr & {{\left( {m + p} \right)^{\,\underline {\,m + l\,} } } \over {\left( {m + l - 1/2} \right)^{\,\underline {\,m + l\,} } }} = {{\left( {m + p} \right)!\left( {m + p - 1/2} \right)^{\,\underline {\,p - l\,} } } \over {\left( {p - l} \right)!\left( {m + p - 1/2} \right)^{\,\underline {\,m + p\,} } }} \cr & \quad \quad \Downarrow \cr & {{\left( {m + p} \right)^{\,\underline {\,m + l\,} } } \over {\left( {m + l} \right)!}}{1 \over {\left( {m + l - 1/2} \right)^{\,\underline {\,m + l\,} } }} = {{\left( {m + p} \right)!} \over {\left( {p - l} \right)!\left( {m + l} \right)!}}{{\left( {m + p - 1/2} \right)^{\,\underline {\,p - l\,} } } \over {\left( {m + p - 1/2} \right)^{\,\underline {\,m + p\,} } }} \cr & \quad \quad \Downarrow \cr & {1 \over {\left( {m + l - 1/2} \right)^{\,\underline {\,m + l\,} } }} = {{\left( {m + p - 1/2} \right)^{\,\underline {\,p - l\,} } } \over {\left( {m + p - 1/2} \right)^{\,\underline {\,m + p\,} } }} \cr & \quad \quad \Downarrow \cr & \left( {m + p - 1/2} \right)^{\,\underline {\,m + p\,} } = \left( {m + p - 1/2} \right)^{\,\underline {\,\,p - l\, + m + l\,} } = \cr & = \left( {m + p - 1/2} \right)^{\,\underline {\,p - l\,} } \left( {m + l - 1/2} \right)^{\,\underline {\,m + l\,} } \cr} } \tag{4}

• The presentation is somewhat unorthodox, but the derivation is clever. (+1) – Markus Scheuer Jan 15 '18 at 21:10
• @MarkusScheuer: Hi Markus, glad to meet again with you (and Marko) on an interesting binomial identity. Yes, at first attempt I did not succeed and find a more straight way: I congratulate with you for finding that (+1). – G Cab Jan 15 '18 at 22:18
• Many thanks for your nice comment. :-) – Markus Scheuer Jan 15 '18 at 22:33