Binomial Identity $\sum\binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$ I'm looking for a reference with the proof of the following binomial identity:
$$\sum_{k=0}^n \binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$$
I've looked in a number of textbooks that have a lot of binomial identities but I can't seem to find this specific one. Any help would be greatly appreciated!
 A: LHS is the coefficient of $z^{2n}$ in
$$
(1+z)^m\frac{(1+\sqrt{1+z})^{2n+1}-(1-\sqrt{1+z})^{2n+1}}{2\sqrt{1+z}}.
$$
Such coefficient can be written as a residue,
$$
\operatorname{res}\left\{
(1+z)^m\frac{(1+\sqrt{1+z})^{2n+1}-(1-\sqrt{1+z})^{2n+1}}{2\sqrt{1+z}}\frac{dz}{z^{2n+1}}
\right\}.
$$
After the substitution $w=\sqrt{1+z}-1$ we get (using $dw=\frac{dz}{2\sqrt{1+z}}$)
$$
\operatorname{res}\left\{
(1+w)^{2m}\frac{(w+2)^{2n+1}-(-w)^{2n+1}}{(w(w+2))^{2n+1}}dw
\right\}
=
\operatorname{res}\left\{
\frac{(1+w)^{2m}}{w^{2n+1}}+
\frac{(1+w)^{2m}}{(2+w)^{2n+1}}
\right\}dw.
$$
The first summand gives the coefficient of $w^{2n}$ in $(1+w)^{2m}$ (i.e. RHS) and the second has zero residue at $w=0$. QED.
A: This can also be done using a basic complex variables technique, which
gives a close variation on what was posted by @GrigoryM.
Suppose we seek to evaluate
$$\sum_{k=0}^n {2n+1\choose 2k+1} {m+k\choose 2n}.$$
Introduce the integral representation
$${m+k\choose 2n}
= \frac{1}{2\pi i} 
\int_{|z|=\varepsilon} \frac{1}{z^{2n+1}} (1+z)^{m+k} \; dz.$$
This gives the following integral
$$\frac{1}{2\pi i} 
\int_{|z|=\varepsilon} 
\sum_{k=0}^n {2n+1\choose 2k+1}
\frac{1}{z^{2n+1}} (1+z)^{m+k} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\varepsilon} \frac{(1+z)^m}{z^{2n+1}}
\sum_{k=0}^n {2n+1\choose 2k+1} (1+z)^k \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\varepsilon} \frac{(1+z)^{m-1/2}}{z^{2n+1}}
\sum_{k=0}^n {2n+1\choose 2k+1} \sqrt{1+z}^{2k+1} \; dz.$$
The sum is
$$\sum_{k=0}^{2n+1} {2n+1\choose k} \sqrt{1+z}^k
\frac{1}{2} (1-(-1)^k)
\\ = \frac{1}{2} ((1+\sqrt{1+z})^{2n+1}
- (1-\sqrt{1+z})^{2n+1})$$
and we get for the integral
$$\frac{1}{2\pi i} 
\int_{|z|=\varepsilon} \frac{(1+z)^{m-1/2}}{2z^{2n+1}}
\left((1+\sqrt{1+z})^{2n+1} - (1-\sqrt{1+z})^{2n+1})\right) \; dz.$$
By  way  of  ensuring  analyticity   we  observe  that  we  must  have
$\varepsilon \lt  1$ owing to  the branch  cut $(-\infty, -1]$  of the
square  root. Now  put $1+z  = w^2$  so that  $dz =  2w\; dw$  and the
integral becomes
$$\frac{1}{2\pi i} 
\int_{|w-1|=\gamma} \frac{w^{2m-1}}{(w^2-1)^{2n+1}}
\left((1+w)^{2n+1} - (1-w)^{2n+1})\right) \; w \; dw.$$
This is
$$\frac{1}{2\pi i} 
\int_{|w-1|=\gamma} w^{2m} 
\left(\frac{1}{(w-1)^{2n+1}} + \frac{1}{(w+1)^{2n+1}}\right) \;  dw.$$
Treat the two terms in the parentheses in turn. The first contributes
$$[(w-1)^{2n}] w^{2m}
= [(w-1)^{2n}] \sum_{q=0}^{2m} {2m\choose q} (w-1)^q
= {2m\choose 2n}.$$
The second term  is analytic on and inside the  circle that $w$ traces
round the value $1$  with no poles (pole is at  $w=-1$) and hence does
not contribute anything.  This concludes the argument.

Remark.  We  must   document  the  choice  of   $\gamma$  so  that
$|w-1|=\gamma$    is   entirely    contained   in    the   image    of
$|z|=\varepsilon$, which since $w=1+\frac{1}{2}  z + \cdots$ makes one
turn around $w=1$ and may then  be continuously deformed to the circle
$|w-1|=\gamma.$ We need  a bound on where this image  comes closest to
one.   We have  $w =  1  + \frac{1}{2}  z +  \sum_{q\ge 2}  (-1)^{q+1}
\frac{1}{4^q} \frac{1}{2q-1}  {2q\choose q}  z^q.$ The modulus  of the
series term is bounded  by $\sum_{q\ge 2} \frac{1}{4^q} \frac{1}{2q-1}
{2q\choose q} |z|^q  = 1 - \frac{1}{2} |z|  - \sqrt{1-|z|}.$ Therefore
choosing   $\gamma  =   \frac{1}{2}\varepsilon  -   1  +   \frac{1}{2}
\varepsilon + \sqrt{1-\epsilon} = \sqrt{1-\varepsilon} + \varepsilon -
1$ will  fit the  bill. For  example with $\varepsilon  = 1/2$  we get
$\gamma = (\sqrt{2}-1)/2.$ It is a matter of arithmetic to verify that
with the formula we have $\gamma \lt 1$.
A: 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.
