If you are tired of trying to find an ingenious proof,
here is a computer-aided procedure for proving the identity.
The nomenclature follows that in Petkovšek, Wilf, Zeilberger (1997): $A=B$.
If you are impatient, just read the introduction to chapter 6.
Set
$$\begin{align}
F(n,k) &= \binom{2n+1}{2k+1}\binom{m+k}{2n}
\\ f(n) &= \sum_{k\in\mathbb{Z}} F(n,k)
\end{align}$$
Here we use $\binom{n}{k}=0$ for $k<0$ as well as for $k>n$.
There will be no need to make the dependency on $m$ explicit.
The claim is $f(n)=\binom{2m}{2n}$
which is equivalent to
$$\begin{align}
f(n) &= 0 &&\text{for $n < 0$} \tag{$-$}
\\ f(n) &= 1 &&\text{for $n = 0$} \tag{0}
\\ f(n+1) &= \frac{(m-n)(2m-2n-1)}{(n+1)(2n+1)} f(n)
&&\text{for $n\geq 0$} \tag{1}
\end{align}$$
$(-)$ and $(0)$ can be verified immediately.
For $(1)$ we will use Zeilberger's method.
Note that $\frac{F(n+1,k)}{F(n,k)}$ and $\frac{F(n,k+1)}{F(n,k)}$
are rational functions of $n$ and $k$, therefore we call $F(n,k)$
a hypergeometric term.
Zeilberger's method finds another hypergeometric term $G(n,k)$ and
$k$-free polynomials $a_0(n),\ldots,a_J(n)$ (also depending on $m$) such that
$$\sum_{j=0}^J a_j(n)\,F(n+j,k) = G(n,k+1) - G(n,k) \tag{2}$$
In fact, we will get
$$G(n,k) = R(n,k)\,F(n,k)$$
where $R(n,k)$ is a rational function in $n$ and $k$.
Consequently. for any given $n$ and $m$, there are finite lower and upper bounds
for those $k$ for which $G(n,k)$ can be nonzero.
Therefore, summing $(2)$ over $k\in\mathbb{Z}$ allows telescoping to
$$\sum_{j=0}^J a_j(n)\,f(n+j) = 0 \tag{3}$$
which is a recurrence relation for $f$.
The claim is that this recurrence relation
yields the same sequence $f(n)$ as $(1)$.
Note that verification of the proof essentially amounts to verification of
$(2)$, which requires no ingenuity because $(2)$ is equivalent to
$$\sum_{j=0}^J a_j(n)\,\frac{F(n+j,k)}{F(n,k)} =
R(n,k+1) \frac{F(n,k+1)}{F(n,k)} - R(n,k) \tag{4}$$
which consists of rational functions only.
It remains to find $R(n,k)$ and $a_0(n),\ldots,a_J(n)$.
This is best done with a suitable computer algebra system.
For example, in Maxima,
or in SAGE on maxima.console()
,
the lines
load(zeilberger);
Zeilberger(binomial(2*n+1,2*k+1)*binomial(m+k,2*n),k,n);
would suffice. But let us be a bit more verbose and also verify the result:
load(zeilberger);
F(n,k) := binomial(2*n+1,2*k+1)*binomial(m+k,2*n);
define (Fn(n,k), factcomb(makefact(F(n+1,k)/F(n,k)))), sumsplitfact:false;
define (Fk(n,k), factcomb(makefact(F(n,k+1)/F(n,k)))), sumsplitfact:false;
sols: Zeilberger(F(n,k),k,n);
/* Pick the first (and only) solution */
sol: sols[1];
/* sol has the form [R(n,k), [a_0, ..., a_J]] */
define (R(n,k), sol[1]);
/* Horner for lhs: sum(a_i*F(n+i,k)/F(n,k),i,0,length(a)-1); */
a: sol[2];
lhs: block([s], s: 0, for i: length(a) step -1 thru 1 do
s: s*Fn(n+(i-1),k)+a[i], s);
/* Here length(a)=2, so we have lhs: a[1]+a[2]*Fn(n,k); */
rhs: R(n,k+1)*Fk(n,k)-R(n,k);
ratsimp(lhs-rhs);
These commands should produce output with last line 0
.
The Zeilberger
results are: $J=1$ and
$$\begin{align}
a_0(n) &= (m-n)(2m-2n-1)
\\ a_1(n) &= -(n+1)(2n+1)
\\ R(n,k) &= \frac{k(2k+1)(2n-m-k)(8n^2-6mn-6kn+10n+4km-5m-3k+3)}
{2(n-k+1)(2n+1)(2n-2k+1)}
\\\therefore\quad
G(n,k) &= -\frac{1}{2}(8n^2-6mn-6kn+10n+4km-5m-3k+3)
\binom{2n+1}{2k-1}\binom{m+k}{2n+1}
\end{align}$$
Note that $G(n,k)$ has the singularities of $R(n,k)$ removed, as it should be,
and that $(3)$ is equivalent to
$$f(n+1) = -\frac{a_0(n)}{a_1(n)} f(n) =
\frac{(m-n)(2m-2n-1)}{(n+1)(2n+1)} f(n)$$
which indeed matches $(1)$.
We should be done now, but you know,
the first way found is usually not the best one.
You will have noticed that $k$ is the summation variable which we want to
telescope, but there is no particular reason for switching to $n$
instead of $m$ for the recurrence.
Let us try switching the recurrence to $m$ instead:
Zeilberger(binomial(2*n+1,2*k+1)*binomial(m+k,2*n),k,m);
This outputs
$$\begin{align}
a_0(m) &= -(m+1)(2m+1)
\\ a_1(m) &= (m-n+1)(2m-2n+1)
\\ R(m,k) &= k(2k+1)
\end{align}$$
which simplifies the proof drastically. And I should have foreseen that.
Well, in the outset I supposed tiredness. Now that is proven too.