35
$\begingroup$

When working on a problem I was faced with the following binomial identity valid for integers $m,n\geq 0$: \begin{align*} \color{blue}{\sum_{l=0}^m(-4)^l\binom{m}{l}\binom{2l}{l}^{-1} \sum_{k=0}^n\frac{(-4)^k}{2k+1}\binom{n}{k}\binom{2k}{k}^{-1}\binom{k+l}{l} =\frac{1}{2n+1-2m}}\tag{1} \end{align*}

I have troubles to prove it and so I'm kindly asking for support.

Maybe the following simpler one-dimensional identity could be useful for a proof. We have for non-negative integers $n$: \begin{align*} \sum_{k=0}^n(-1)^k\binom{n}{k}\frac{1}{2k+1}=\frac{4^{n}}{2n+1}\binom{2n}{n}^{-1}\tag{2} \end{align*}

The LHS of (2) can be transformed to \begin{align*} \sum_{k=0}^n(-1)^k\binom{n}{k}\frac{1}{2k+1}&=\sum_{k=0}^n(-1)^k\binom{n}{k}\int_{0}^1x^{2k}dx\\ &=\int_{0}^1\sum_{k=0}^n(-1)^k\binom{n}{k}x^{2k}\,dx\\ &=\int_{0}^1(1-x^2)^n\,dx \end{align*}

Using a well-known integral representation of reciprocals of binomial coefficients the RHS of (2) can be written as \begin{align*} \frac{4^{n}}{2n+1}\binom{2n}{n}^{-1}&=4^n\int_{0}^1x^n(1-x)^n\,dx \end{align*} and the equality of both integrals can be shown easily. From (2) we can derive a simple one-dimensional variant of (1).

We consider binomial inverse pairs and with respect to (2) we obtain

\begin{align*} &f_n=\sum_{k=0}^n(-1)^k\binom{n}{k}g_k \quad&\quad g_n=\sum_{k=0}^n(-1)^k\binom{n}{k}f_k\\ &f_n=\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{1}{2k+1} \quad&\quad\frac{1}{2n+1}=\sum_{k=0}^n(-1)^k\binom{n}{k}f_k \end{align*}

We conclude again with (2) \begin{align*} \frac{1}{2n+1}&=\sum_{k=0}^n(-1)^k\binom{n}{k}f_k\\ &=\sum_{k=0}^n\frac{(-4)^{k}}{2k+1}\binom{n}{k}\binom{2k}{k}^{-1}\\ \end{align*} This identity looks somewhat like a one-dimensional version of (1). Maybe this information can be used to solve (1).

$\endgroup$
  • $\begingroup$ nice question (+1). is it possible to generalize your 1d identity to the case where $4$ is replaced by some variable $y$? $\endgroup$ – tired Aug 6 '17 at 22:58
  • $\begingroup$ What's the source of this identity? $\endgroup$ – Alex R. Aug 7 '17 at 17:36
  • $\begingroup$ @tired: The factor $4$ seems to be essential due to a transformation of the beta function preserving symmetry. See the comment (2) in my contribution which is in fact a meditation about MarkoRiedels answer. $\endgroup$ – Markus Scheuer Aug 15 '17 at 20:03
  • $\begingroup$ @AlexR.: It is an intermediate result of this MSE post. $\endgroup$ – Markus Scheuer Aug 15 '17 at 20:05
18
$\begingroup$

We seek to evaluate

$$\sum_{l=0}^m (-4)^l {m\choose l} {2l\choose l}^{-1} \sum_{k=0}^n \frac{(-4)^k}{2k+1} {n\choose k} {2k\choose k}^{-1} {k+l\choose l}.$$

We start with the inner term and use the Beta function identity

$$\frac{1}{2k+1} {2k\choose k}^{-1} = \int_0^1 x^k (1-x)^k \; dx.$$

We obtain

$$\int_0^1 [z^l] \sum_{k=0}^n {n\choose k} (-4)^k x^k (1-x)^k \frac{1}{(1-z)^{k+1}} \; dx \\ = [z^l] \frac{1}{1-z} \int_0^1 \left(1-\frac{4x(1-x)}{1-z}\right)^n \; dx \\ = [z^l] \frac{1}{(1-z)^{n+1}} \int_0^1 ((1-2x)^2-z)^n \; dx \\ = \sum_{q=0}^l {l-q+n\choose n} [z^q] \int_0^1 ((1-2x)^2-z)^n \; dx \\ = \sum_{q=0}^l {l-q+n\choose n} {n\choose q} (-1)^q \int_0^1 (1-2x)^{2n-2q} \; dx \\ = \sum_{q=0}^l {l-q+n\choose n} {n\choose q} (-1)^q \left[-\frac{1}{2(2n-2q+1)} (1-2x)^{2n-2q+1}\right]_0^1 \\ = \sum_{q=0}^l {l-q+n\choose n} {n\choose q} (-1)^q \frac{1}{2n-2q+1}.$$

Now we have

$$ {l-q+n\choose n} {n\choose q} (-1)^q \frac{1}{2n-2q+1} \\ = \mathrm{Res}_{z=q} \frac{(-1)^n}{2n+1-2z} \prod_{p=0}^{n-1} (l+n-p-z) \prod_{p=0}^n \frac{1}{z-p}.$$

Residues sum to zero and since $\lim_{R\to\infty} 2\pi R \times R^n / R / R^{n+1} = 0$ we may evaluate the sum using the negative of the residue at $z=(2n+1)/2.$ We get

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

We obtain for our sum

$$(-1)^n 2^{2n+1} {2n+1\choose n}^{-1} \sum_{l=0}^m (-4)^l {m\choose l} \frac{1}{2l+1} {2l\choose l}^{-1} {l+1/2\choose n+1}.$$

We now work with the remaining sum without the factor in front. We obtain

$$\int_0^1 [z^{n+1}] \sqrt{1+z} \sum_{l=0}^m {m\choose l} (-4)^l x^l (1-x)^l (1+z)^l \; dx \\ = [z^{n+1}] \sqrt{1+z} \int_0^1 (1-4x(1-x)(1+z))^m \; dx \\ = [z^{n+1}] \sqrt{1+z} \int_0^1 \sum_{q=0}^m {m\choose q} (1-2x)^{2m-2q} (-1)^q (4x(1-x))^q z^q \; dx \\ = \sum_{q=0}^m {m\choose q} {1/2\choose n+1-q} \int_0^1 (1-2x)^{2m-2q} (-1)^q (4x(1-x))^q \; dx \\ = \sum_{q=0}^m {m\choose q} {1/2\choose n+1-q} \int_0^1 (1-2x)^{2m} \left(1-\frac{1}{(1-2x)^2}\right)^q \; dx \\ = \sum_{q=0}^m {m\choose q} {1/2\choose n+1-q} \sum_{p=0}^q {q\choose p} (-1)^p \int_0^1 (1-2x)^{2m-2p} \; dx \\ = \sum_{q=0}^m {m\choose q} {1/2\choose n+1-q} \sum_{p=0}^q {q\choose p} (-1)^p \frac{1}{2m-2p+1}.$$

Re-writing then yields

$$\sum_{p=0}^m (-1)^p \frac{1}{2m-2p+1} \sum_{q=p}^m {m\choose q} {1/2\choose n+1-q} {q\choose p}.$$

Observe that

$${m\choose q} {q\choose p} = \frac{m!}{(m-q)! \times p! \times (q-p)!} = {m\choose p} {m-p\choose m-q}$$

so that we find

$$\sum_{p=0}^m {m\choose p} (-1)^p \frac{1}{2m-2p+1} \sum_{q=p}^m {m-p\choose m-q} {1/2\choose n+1-q} \\ = \sum_{p=0}^m {m\choose p} (-1)^p \frac{1}{2m-2p+1} \sum_{q=0}^{m-p} {m-p\choose m-p-q} {1/2\choose n+1-p-q} \\ = \sum_{p=0}^m {m\choose p} (-1)^p \frac{1}{2m-2p+1} \sum_{q=0}^{m-p} {m-p\choose q} {1/2\choose n+1-p-q}.$$

Continuing we obtain

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

Concluding with a closed form we establish at last

$$(-1)^m \frac{1}{2m-2n-1} \sum_{p=0}^m {m\choose p} (-1)^p [z^{n+1-m}] z^{-p} (1+z)^{p-1/2} \\ = (-1)^m \frac{1}{2m-2n-1} [z^{n+1-m}] (1+z)^{-1/2} \sum_{p=0}^m {m\choose p} (-1)^p z^{-p} (1+z)^p \\ = (-1)^m \frac{1}{2m-2n-1} [z^{n+1-m}] (1+z)^{-1/2} \left(1-\frac{1+z}{z}\right)^m \\ = \frac{1}{2m-2n-1} [z^{n+1}] (1+z)^{-1/2}.$$

We finish by re-introducing the factor in front to obtain

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

Yes indeed this is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n+1-2m}.}$$

Here I have chosen to document the simple steps as well as the complicated ones to aid all types of readers.

$\endgroup$
  • $\begingroup$ Checked and verified. . . . and . . . what a pleasure to go through this wonderful demonstration of your art! In fact I was hoping for a contribution also from your side. The steps are crystal clear and I see now what I have to do to overcome the problems I had. This will clearly raise my skills. Thanks a lot, Marko. :-) $\endgroup$ – Markus Scheuer Aug 8 '17 at 6:55
  • $\begingroup$ Thank you. I have also profited from the experience. As an auxiliary observation, it was interesting to see that in fact the number four plays a special role here. $\endgroup$ – Marko Riedel Aug 8 '17 at 12:20
  • $\begingroup$ Yes, you're right. Especially for square completion. $\endgroup$ – Markus Scheuer Aug 8 '17 at 12:38
6
$\begingroup$

Note:

The following is based on the great answer of @MarkoRiedel. I did a rather detailed inspection of his steps and checked for alternatives resp. simplifications by keeping the thread of his ideas.

In fact besides small changes partly due to symmetry of a transformed version of the beta function, only in the second part a few lines could be simplified using Vandermonde's identity instead.

Nevertheless the following might be useful for some readers as supplement to his answer. The naming scheme is the same in order to ease comparison.


We show the identity \begin{align*} \sum_{l=0}^m(-4)^l\binom{m}{l}\binom{2l}{l}^{-1} \sum_{k=0}^n\frac{(-4)^k}{2k+1}\binom{n}{k}\binom{2k}{k}^{-1}\binom{k+l}{l} =\frac{1}{2n+1-2m} \end{align*} by first deriving a closed formula for the inner sum.

First step: Inner sum

The following is valid for integral $n,l\geq 0$: \begin{align*} \color{blue}{\sum_{k=0}^n\frac{(-4)^k}{2k+1}\binom{n}{k}\binom{2k}{k}^{-1}\binom{k+l}{l} =\frac{(-4)^n}{2n+1}\binom{2n}{n}^{-1}\binom{l-\frac{1}{2}}{n}}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\frac{(-4)^k}{2k+1}\binom{n}{k}\binom{2k}{k}^{-1}\binom{k+l}{l}}\\ &=\sum_{k=0}^n(-1)^k\binom{n}{k}\int_{0}^1(1-x^2)^k\,dx[z^l]\frac{1}{(1-z)^{k+1}}\tag{2}\\ &=[z^l]\frac{1}{1-z}\int_{0}^1\sum_{k=0}^n\binom{n}{k}\left(-\frac{1-x^2}{1-z}\right)^k\,dx\tag{3}\\ &=[z^l]\frac{1}{1-z}\int_0^1\left(1-\frac{1-x^2}{1-z}\right)^n\,dx\\ &=[z^l]\frac{1}{(1-z)^{n+1}}\int_0^1\left(x^2-z\right)^n\,dx\\ &=\sum_{q=0}^l\left([z^{l-q}]\frac{1}{(1-z)^{n+1}}\right)\left([z^q]\int_0^1\left(x^2-z\right)^n\,dx\right)\tag{4}\\ &=\sum_{q=0}^l\binom{l-q+n}{n}\int_0^1\binom{n}{q}(-1)^qx^{2n-2q}\,dx\tag{5}\\ &\color{blue}{=\sum_{q=0}^l\binom{l-q+n}{n}\binom{n}{q}(-1)^q\frac{1}{2n-2q+1}}\tag{6}\\ &=\sum_{q=0}^l\mathrm{Res}\left(\frac{(-1)^n}{2n+1-2z}\prod_{p=0}^{n-1}(l+n-p-z)\prod_{p=0}^n\frac{1}{z-p};z=q\right)\tag{7}\\ &=-\mathrm{Res}\left(\frac{(-1)^n}{2n+1-2z}\prod_{p=0}^{n-1}(l+n-p-z)\prod_{p=0}^n\frac{1}{z-p};z=\frac{2n+1}{2}\right)\tag{8}\\ &=\frac{(-1)^n}{2}\prod_{p=0}^{n-1}\left(l+n-p-\frac{2n+1}{2}\right)\prod_{p=0}^n\frac{1}{\frac{2n+1}{2}-p}\tag{9}\\ &=(-2)^n\prod_{p=0}^{n-1}\left(l-p-\frac{1}{2}\right)\prod_{p=0}^n\frac{1}{2p+1}\\ &=\frac{(-2)^n}{(2n+1)!!}\prod_{p=0}^{n-1}\left(l-p-\frac{1}{2}\right)\tag{10}\\ &\color{blue}{=\frac{(-4)^n}{2n+1}\binom{2n}{n}^{-1}\binom{l-\frac{1}{2}}{n}}\tag{11} \end{align*} and the claim (1) follows.

Comment:

  • In (2) we apply the coefficient of operator and use a transformation of the beta function identity \begin{align*} \binom{2n}{n}^{-1}&=(2n+1)\int_{0}^1x^n(1-x)^n\,dx\\ &=\frac{2n+1}{4^n}\int_{0}^1(1-x^2)^n\,dx \end{align*}

This is the first cool representation of a binomial coefficient.

  • In (3) we do some rearrangements in order to apply the binomial theorem in the next line.

In the next steps we consequently use a divide and conquer strategy in order to separate $x$ and $z$.

  • In (4) we use the product rule \begin{align*} [z^l]\left(A(z)B(z)\right)=\sum_{q=0}^l\left([z^q]A(z)\right)\left([z^{l-q}]B(z)\right) \end{align*} of the coefficient of operator.

  • In (5) we select the coefficient of $z^{l-q}$ in the left factor and apply the binomial theorem to the right factor and select the coefficient of $z^q$.

  • In (6) we integrate and evalute the expression. This intermediate step is already a nice identity and therefore colorized.

  • In (7) we use another cool representation of binomial coefficients namely as residue of a meromorphic function. \begin{align*} \binom{n}{k}=(-1)^{n-k}n!\mathrm{Res}\left(\prod_{q=0}^n\frac{1}{z-q};z=k\right) \end{align*} Note that $\prod_{q=0}^n\frac{1}{z-q}$ is a meromorphic function with $n+1$ simple poles at $q=0,\ldots,n$. We obtain \begin{align*} (-1)^{n-k}n!&\mathrm{Res}\left(\prod_{q=0}^n\frac{1}{z-q};z=k\right)\\ &=(-1)^{n-k}n!\lim_{z\rightarrow k}\left((z-k)\prod_{q=0}^n\frac{1}{z-q}\right)\\ &=(-1)^{n-k}n!\cdot\frac{1}{k\cdot(k-1)\cdots 1}\cdot\frac{1}{(-1)(-2)\cdots(k-n)}\\ &=(-1)^{n-k}\frac{n!}{k!(-1)^{n-k}(n-k)!}\\ &=\binom{n}{k} \end{align*}
  • In (8) we use a theorem of complex analysis telling us that the sum of the residues at the poles of a meromorphic function together with the residue at infinity sums up to zero. Here we have simple poles at $q=0,\ldots, n$ and at $q=\frac{2n+1}{2}$. We show the residue at infinity is zero and since the other residuals sum up to zero we have the situation \begin{align*} \sum_{q=0}^n\mathrm{Res}\left(f(z);z=q\right)=-\mathrm{Res}\left(f(z);z=\frac{2n+1}{2}\right) \end{align*} and we can so get rid of the sum. In order to show that the residue at infinity vanishes we use the following formula: \begin{align*} \mathrm{Res}(f(z);z=\infty)&=\mathrm{Res}\left(-\frac{1}{z^2}f\left(\frac{1}{z}\right);z=0\right)\\ &=[z^{-1}]\left(-\frac{1}{z^2}f\left(\frac{1}{z}\right)\right) \end{align*} We obtain \begin{align*} [z^{-1}]&\left(-\frac{1}{z^2}\cdot\frac{(-1)^n}{2n+1-\frac{2}{z}}\prod_{p=0}^{n-1}\left(l+n-p-\frac{1}{z}\right)\prod_{p=0}^n\frac{1}{\frac{1}{z}-p}\right)\\ &=[z^{-1}]\frac{1}{z^2}\cdot\frac{(-1)^{n+1}z}{(2n+1)z-2}\left(z^{-n}\prod_{p=0}^{n-1}\left((l+n-p)z-1\right)\right) \left(z^{n+1}\prod_{p=0}^n\frac{1}{1-pz}\right)\\ &=-[z^{-1}]\frac{(-1)^n}{(2n+1)z-2}\prod_{p=0}^{n-1}\left((l+n-p)z-1\right)\prod_{p=0}^n\frac{1}{1-pz}\\ &=0 \end{align*} The coefficient of $z^{-1}$ is zero since the function is holomorphic as the product of a polynomial and geometric series.

  • In (9) we evaluate the function at the residue $z=\frac{n+1}{2}$.

  • In (10) we use the double factorial $(2n+1)!!=(2n+1)(2n-1)\cdots 3\cdot1$.

Intermezzo: We also want to use the transformed beta function in the second step. It is convenient to use a slightly different representation as that given in (11). The following can be shown by elementary transformations \begin{align*} \frac{(-4)^n}{2n+1}\binom{2n}{n}^{-1}\binom{l-\frac{1}{2}}{n} &=(-1)^n2^{2n+1}\binom{2n+1}{n}^{-1}\frac{1}{2l+1}\binom{l+\frac{1}{2}}{n+1}\tag{12}\\ &=-\binom{-\frac{1}{2}}{n+1}^{-1}\frac{1}{2l+1}\binom{l+\frac{1}{2}}{n+1}\tag{13} \end{align*}

We have simplified the inner sum of the double sum stated in the question and obtained expression (11). The double sum can now be written using (12) as \begin{align*} \sum_{l=0}^m&(-4)^l\binom{m}{l}\binom{2l}{l}^{-1} \sum_{k=0}^n\frac{(-4)^k}{2k+1}\binom{n}{k}\binom{2k}{k}^{-1}\binom{k+l}{l}\\ &=(-1)^n2^{2n+1}\binom{2n+1}{n}^{-1}\sum_{l=0}^m\frac{(-4)^l}{2l+1}\binom{m}{l}\binom{2l}{l}^{-1}\binom{l+\frac{1}{2}}{n+1}\tag{14} \end{align*}

Second step: Double sum

We start with the right-hand side of (14) but without respecting the factor $(-1)^n2^{2n+1}\binom{2n+1}{n}^{-1}$. This factor will be considered at the end. \begin{align*} \color{blue}{\sum_{l=0}^m}&\color{blue}{(-4)^l\binom{m}{l}\frac{1}{2l+1}\binom{2l}{l}^{-1}\binom{l+\frac{1}{2}}{n+1}}\\ &=\sum_{l=0}^m(-1)^l\binom{m}{l}\int_0^1(1-x^2)^l\,dx[z^{n+1}](1+z)^{l+\frac{1}{2}}\tag{15}\\ &=[z^{n+1}]\sqrt{1+z}\int_0^1\sum_{l=0}^m\binom{m}{l}\left(-(1-x^2)(1+z)\right)^l\,dx\tag{16}\\ &=[z^{n+1}]\sqrt{1+z}\int_0^1(1-(1-x^2)(1+z))^m\,dx\\ &=[z^{n+1}]\sqrt{1+z}\int_0^1\sum_{q=0}^m\binom{m}{q}(-(1-x^2)z)^qx^{2m-2q}\,dx\\ &=\sum_{q=0}^m\binom{m}{q}(-1)^q[z^{n+1-q}]\sqrt{1+z}\int_0^1(1-x^2)^qx^{2m-2q}\,dx\\ &=\sum_{q=0}^m\binom{m}{q}(-1)^q\binom{\frac{1}{2}}{n+1-q}\int_0^1\sum_{p=0}^q\binom{q}{p}(-x^2)^{q-p}x^{2m-2q}\,dx\tag{17}\\ &=\sum_{q=0}^m\binom{m}{q}\binom{\frac{1}{2}}{n+1-q}\sum_{p=0}^q(-1)^p\binom{q}{p}\frac{1}{2m-2p+1}\tag{18}\\ &=\sum_{p=0}^m\sum_{q=p}^m\binom{m}{p}\binom{m-p}{q-p}\binom{\frac{1}{2}}{n+1-q}(-1)^p\frac{1}{2m-2p+1}\tag{19}\\ &=\sum_{p=0}^m(-1)^p\frac{1}{2m-2p+1}\binom{m}{p}\sum_{q=0}^{m-p}\binom{m-p}{q}\binom{\frac{1}{2}}{n+1-q-p}\\ &=\sum_{p=0}^m(-1)^p\frac{1}{2m-2p+1}\binom{m}{p}\binom{m-p+\frac{1}{2}}{n+1-p}\tag{20}\\ &=\frac{1}{2m-2n-1}\sum_{p=0}^m(-1)^p\binom{m}{p}\binom{m-p-\frac{1}{2}}{n+1-p}\tag{21}\\ &=\frac{(-1)^m}{2m-2n-1}\sum_{p=0}^m(-1)^p\binom{m}{p}\binom{p-\frac{1}{2}}{n+1-m-p}\tag{22}\\ &=\frac{(-1)^m}{2m-2n-1}\sum_{p=0}^m(-1)^p\binom{m}{p}[z^{n+1-m}]z^{-p}\left(1+z\right)^{p-\frac{1}{2}}\tag{23}\\ &=\frac{(-1)^m}{2m-2n-1}[z^{n+1-m}](1+z)^{-\frac{1}{2}}\sum_{p=0}^m(-1)^p\binom{m}{p}\left(\frac{1+z}{z}\right)^p\\ &=\frac{(-1)^m}{2m-2n-1}[z^{n+1-m}](1+z)^{-\frac{1}{2}}\left(1-\frac{1+z}{z}\right)^m\\ &=\frac{1}{2m-2n-1}[z^{n+1}](1+z)^{-\frac{1}{2}}\\ &\color{blue}{=\frac{-1}{2n+1-2m}\binom{-\frac{1}{2}}{n+1}} \end{align*} and the claim follows when respecting the factor $-\binom{-\frac{1}{2}}{n+1}^{-1}$ stated in (13) together with (14).

Comment:

  • In (15) we apply the coefficient of operator and use a transformation of the beta function identity as we did in (2).

  • In (16) we factor out the $\sqrt{z+1}$ and do some rearrangements in order to apply the binomial theorem in the next line.

In the next lines we again use the divide and conquer strategy to separate $x$ and $z$.

  • In (17) we select the coefficient of $z^{n+1-q}$ and apply the binomial theorem again.

  • In (18) we integrate and evaluate the expression.

  • In (19) we change the order of the sums and apply the binomial identity \begin{align*} \binom{m}{q}\binom{q}{p}=\binom{m}{p}\binom{m-p}{q-p} \end{align*}

  • In (20) we apply Vandermonde's Identity.

  • In (21) we use the binomial identity \begin{align*} \binom{\alpha}{n}=\frac{\alpha}{\alpha-n}\binom{\alpha-1}{n} \end{align*}

  • In (22) we change the order of summation by replacing $p\rightarrow m-p$.

  • In (23) we apply the coefficient of operator the last time.

$\endgroup$
  • $\begingroup$ Thank you for this very useful work. (+1). I think your readers will definitely profit from seeing the alternate residue formula for the binomial coefficient, which I omitted and your explanation of the residue at infinity. $\endgroup$ – Marko Riedel Aug 15 '17 at 18:54
  • $\begingroup$ @MarkoRiedel: My pleasure! :-) Regarding the factor $4$ in your comment, here it is swallowed by the more symmetrical representation of the beta function right from the beginning. Btw, hints for syntactical improvements or other style issues are always welcome. $\endgroup$ – Markus Scheuer Aug 15 '17 at 19:08
  • $\begingroup$ It was a pleaure to work through this! Very happy that I took a look at it, I hope that I will be able to make use of these tricks sooner or later. $\endgroup$ – Gesbesgue Sep 20 '17 at 20:30
  • $\begingroup$ @Gesbesgue: Many thanks for your nice comment. :-) You might be interested to see another important technique called change of variable formula given in this answer. $\endgroup$ – Markus Scheuer Sep 20 '17 at 20:48
4
$\begingroup$

Let us complete the OP's work, started with $$ \frac{1}{2k+1}\stackrel{\text{Binomial transform}}{\longleftrightarrow} \frac{4^k}{(2k+1)\binom{2k}{k}}\tag{$d=0$}$$ by computing first the binomial transform of $\frac{1}{2k+3}$. We have: $$\begin{eqnarray*}\sum_{k=0}^{n}\frac{(-1)^k}{2k+3}\binom{n}{k}=\int_{0}^{1}x^2(1-x^2)^n=\frac{B\left(n+1,\tfrac{3}{2}\right)}{2}=\frac{1}{2n+3}\cdot\frac{B\left(n+1,\frac{1}{2}\right)}{2}\end{eqnarray*}$$ hence: $$ \frac{1}{2k+3}\stackrel{\text{Binomial transform}}{\longleftrightarrow} \frac{4^k}{(2k+1)(2k+3)\binom{2k}{k}}\tag{$d=1$}$$ and in general: $$ \frac{1}{2k+2d+1}\stackrel{\text{Binomial transform}}{\longleftrightarrow} \frac{4^k\binom{k+d}{d}\binom{2k}{k}^{-1}}{(2k+2d+1)\binom{2k+2d}{2d}}\tag{$d\geq 1$}$$

I need some time to check the above computations, but the last identity, together with creative telescoping, should be the key for proving OP's statement. Indeed, we have: $$ \sum_{k=0}^{n}\frac{(-4)^k}{(2k+1)\binom{2k}{k}}\binom{n}{k}=\frac{1}{2n+1}\tag{$l=0$} $$ $$ \sum_{k=0}^{n}\frac{(-4)^k}{(2k+1)\binom{2k}{k}}\binom{n}{k}(k+1)=-\frac{1}{(2n+1)(2n-1)}\tag{$l=1$} $$

$$\begin{eqnarray*} \sum_{k=0}^{n}\frac{(-4)^k}{(2k+1)\binom{2k}{k}}\binom{n}{k}\binom{k+l}{l}&=&\frac{(-1)^l(2l-1)!!(2n-2l+1)!! }{(2n+1)!!}\\ &=&\frac{(-1)^l 4^{n-l} n! (2l)! (n-l)!}{(2n+1)!l! (2n-2l+1)!}\tag{$l\geq 1$} \end{eqnarray*}$$ hence the whole problem boils down to computing:

$$ \frac{4^n}{(2n+1)\binom{2n}{n}}\sum_{l=0}^{m}\frac{\binom{m}{l}}{(2n-2l+1)!\binom{n}{l}}$$

$\endgroup$
  • $\begingroup$ @JackDAurizio: Nice and creative approach! Thanks a lot, Jack! (+1) This technique will soon be standard part of my repertoire. :-) $\endgroup$ – Markus Scheuer Aug 7 '17 at 21:02
  • $\begingroup$ @MarkusScheuer: you're welcome, Markus. Would you mind checking my answer to this similar question (math.stackexchange.com/a/2386014/44121), too? I got a downvote but I cannot understand why, and you certainly are the right person to help me. $\endgroup$ – Jack D'Aurizio Aug 7 '17 at 21:05
  • $\begingroup$ Very useful notation, $\stackrel{\text{Binomial transform}}{\longleftrightarrow}$. $\endgroup$ – hypergeometric Aug 8 '17 at 6:49
2
$\begingroup$

This is by no means an answer, but may help. Equation (6.28) here is most likely a corollary of Vandermonde's identity with appropriate values for the parameters, but it's too late for me to figure out what they are. This reduces your sum to $$\frac{2^{2n}}{(2n+1)}\binom{2n}{n}^{-1}\sum_{l=0}^m (-4)^l \binom{m}{l}\binom{2l}{l}^{-1}\binom{n-l-\frac{1}{2}}{n}.$$ By the way, Mathematica can evaluate this sum, giving (almost) your right-hand side.

$\endgroup$
  • $\begingroup$ Good reference, thanks! (+1) This is a considerable simplification which makes the problem managable, I think. The upper limit of the sum should be $m$ instead of $n$. $\endgroup$ – Markus Scheuer Aug 7 '17 at 6:51
  • 1
    $\begingroup$ @MarkusScheuer You're welcome. If you'd post an answer when you have one, I'd love to see it. $\endgroup$ – rogerl Aug 7 '17 at 12:22
  • 1
    $\begingroup$ Question answered. Main contribution from Marko Riedel. Best, $\endgroup$ – Markus Scheuer Aug 16 '17 at 9:57
2
$\begingroup$

Firstly let us evaluate the inner sum on the left hand side. Using the beta function identity quoted above along with the identity $\left. \binom{k+l}{l} = d^l/dx^l x^{k+l}/l! \right|_{x=1}$ we have: \begin{equation} S^{(n)}_l:=\sum\limits_{k=0}^n \frac{(-4)^k}{2k+1} \binom{n}{k} [\binom{2k}{k}]^{-1} \binom{k+l}{l} = \left.\frac{1}{l!} \frac{d^l}{d x^l} x^l \int\limits_0^1 \left(1- 4 t (1-t) x\right)^n dt \right|_{x=1} \end{equation} Now if we take $m=0$ then $l=0$ and then: \begin{equation} rhs= 4^n \int\limits_0^1 \left[ (t-\frac{1}{2})^2 \right]^n dt= 4^n \int\limits_{-\frac{1}{2}}^{\frac{1}{2}} u^{2 n} du = \frac{1}{2 n+1} \end{equation} as it should be.

Now let us take arbitrary $l \ge 0$ . Then by using the chain rule of differentiation and then by substituting $u := t-1/2$ we have: \begin{equation} S^{(n)}_l= \sum\limits_{p=0}^l \binom{l}{p} \binom{n}{p} \int\limits_{-\frac{1}{2}}^{\frac{1}{2}} (4 u^2)^{n-p}(4 u^2-1)^p d u \end{equation} Therefore the left hand side of the identity to be proved reads: \begin{eqnarray} &&\sum\limits_{l=0}^m (-4)^l \binom{m}{l} [\binom{2 l}{l}]^{-1} S^{(n)}_l=\\ &&\sum\limits_{p=0}^m(-1)^{p+1} 2^{2p-1} \frac{\binom{m}{p} (m-p-3/2)!(p-1/2)!}{\sqrt{\pi} \binom{2 p}{p} (m-1/2)!} \binom{n}{p} \int\limits_{-\frac{1}{2}}^{\frac{1}{2}} (4 u^2)^{n-p} (4 u^2-1)^p du=\\ &&\sum\limits_{p=0}^m (-1)^{p+1} 4^p \frac{\binom{m}{p} \binom{m}{1/2}}{\binom{2 p}{p} \binom{m}{p+3/2}} \cdot \frac{1}{(2p+1)(2p+3)} \binom{n}{p} \int\limits_{-\frac{1}{2}}^{\frac{1}{2}} (4 u^2)^{n-p} (4 u^2-1)^p du=\\ &&-4^n \sum\limits_{p=0}^m \binom{m}{p} \frac{\binom{n}{p} \binom{m}{1/2}}{\binom{2 p}{p} \binom{m}{p+3/2}} \cdot \frac{1}{(2p+1)(2p+3)} \int\limits_{-\frac{1}{2}}^{\frac{1}{2}} u^{2n-2p} (1-4 u^2)^p du=\\ &&-4^n \frac{1}{2} \frac{n!}{(m-1/2)!} \sum\limits_{p=0}^m \binom{m}{p} \frac{(m-p-3/2)!}{(n-p)!} \int\limits_{-\frac{1}{2}}^{\frac{1}{2}} (u^2)^{n-p} (1/4 - u^2)^p d u=\\ && -\frac{1}{4} \frac{n! m!}{(n+1/2)! (m-1/2)!} \sum\limits_{p=0}^m \frac{(m-p-3/2)!(n-p-1/2)!}{(n-p)!(m-p)!}=\\ && -\frac{1}{(2m-1)(2n+1)} F^{3,2}\left[\begin{array}{rrr} 1&-m&-n\\ \frac{3}{2}-m & \frac{1}{2}-n & \end{array};1\right] = \\ && -\frac{1}{(2m-1)(2n+1)} \cdot \frac{(\frac{1}{2}-m)^{(n)} (\frac{3}{2})^{(n)}}{(\frac{3}{2}-m)^{(n)} (\frac{1}{2})^{(n)}} = \\ &&-\frac{1}{(2m-1)(2n+1)} \cdot \frac{(1- 2m)(1+2 n)}{1-2 m+2 n} = \frac{1}{2n-2 m+1} \end{eqnarray} where in the first line we summed over $l$ and in the second in the third and in the forth lines we simplified the result. Finally in the fifth line we evaluated the integral by substituting for $4 u^2$ and in the subsequent line we expressed the sum through hypergeometric functions. Finally, from Wolfram's site http://functions.wolfram.com/HypergeometricFunctions/Hypergeometric3F2/03/02/04/, we used the following identity: \begin{equation} F^{(3,2)}\left[ \begin{array}{rrr} a& b & -n \\ d & a+b-d-n+1 & \end{array};1 \right] = \frac{(d-a)^{(n)}(d-b)^{(n)}}{(d)^{(n)} (-a-b+d)^{(n)}} \end{equation} for $a=1$, $b=-m$ and $d=3/2-m$.

$\endgroup$
  • $\begingroup$ Interesting approach. Thanks a lot! I will go through it in more detail soon. Good to see that many different solutions. :-) (+1) $\endgroup$ – Markus Scheuer Aug 9 '17 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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