A nice but somewhat challenging binomial identity

Solution 1:

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.

Solution 2:

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.

Solution 3:

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