How to prove this summation formula? Mathematica is able to calculate the following sum:
\begin{align}
 &\sum_{k,l=0}^{n,m}\frac{(-1)^{n+m-l-k}(2m)!(2n+1)!(2 )^{2k+2l}}{(2k+1)!(2l)!(n-k)!(m-l)!}(k+l)!  \nonumber\\
 =&\frac{(-1)^{m+n}2^{2m+2n+1}}{\pi(2n+1-2m)}\Gamma(m+\frac 1 2)\Gamma(n+1+\frac 1 2)  \nonumber\\
 =&\frac{(-2) ^{m+n}(2m-1)!!(2n+1)!!}{(2n+1-2m)}
 \end{align}
(The last step is just a way of re-writing it in terms of double factorial.)
I tried proving it (without putting in too much effort, however) but was not succesful. 
Do you have hints how this should be approached (or even full solutions)? 
I tried complete induction but ended up at a point where I would have had to prove a slightly less difficult summation formula.
 A: We  consider the identity  in the form
\begin{align*}
&\sum_{k,l=0}^{n,m}\frac{(-1)^{n+m-l-k}(2m)!(2n+1)!2^{2k+2l}}{(2k+1)!(2l)!(n-k)!(m-l)!}(k+l)!=\frac{(-2) ^{m+n}(2m-1)!!(2n+1)!!}{2n+1-2m}
\end{align*}

We divide both sides by $(-2)^{m+n}(2m-1)!!(2n+1)!!$ and obtain
  \begin{align*}
\frac{(2m)!(2n+1)!}{2^{m+n}(2m-1)!!(2n+1)!!}\sum_{k,l=0}^{n,m}\frac{(-4)^{k+l}(k+l)!}{(2k+1)!(2l)!(n-k)!(m-l)!}
=\color{blue}{\frac{1}{2n+1-2m}}
\end{align*}
  We start with the left-hand side and we obtain
  \begin{align*}
&\frac{(2m)!(2n+1)!}{2^{m+n}(2m-1)!!(2n+1)!!}\sum_{k,l=0}^{n,m}\frac{(-4)^{k+l}(k+l)!}{(2k+1)!(2l)!(n-k)!(m-l)!}\\
&\qquad=\frac{(2m)!!(2n)!!}{2^{m+n}}\sum_{l=0}^m\frac{(-4)^l}{(2l)!(m-l)!}\sum_{k=0}^n\frac{(-4)^k(k+l)!}{(2k+1)!(n-k)!}\tag{1}\\
&\qquad=m!n!\sum_{l=0}^m\frac{(-4)^l}{(m-l)!l!l!}\binom{2l}{l}^{-1}
\sum_{k=0}^n\frac{(-4)^k}{2k+1}\binom{2k}{k}^{-1}\frac{(k+l)!}{(n-k)!k!k!}\tag{2}\\
&\qquad\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}}
\end{align*}
The equality of the last line with $\color{blue}{\frac{1}{2n+1-2m}}$ is given in this MSE post.

Comment:


*

*In (1) we use the identity $n!=n!!(n-1)!!$

*In (2) we use $(2n)!!=2^nn!$
A: I do not think simple induction will work. I have reduced it to the identity
$$ 1 = \sum_{k=0}^n \sum_{j=0}^m \frac{(-4)^{k+j}(k+j)!(n)!(m)!(2n+1-2m)}
{(2k+1)!(2j)!(n-k)!(m-j)!} $$
for all $n\ge 0, m\ge 0$. The Wilf-Zeilberger
method could prove this but it is not satisfying to me.
