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!

-
Proofs of identities like that are algorithmic and are implemented in many symbolic computations softwares. So, a reference, to make sure it is true, could be inputting it in Mathematica, or wolfram-alpha. Or do you need to reference to learn a proof yourself. – Mlazhinka Shung Gronzalez LeWy Dec 10 '13 at 22:41
Mathematica confirms immediately. – Igor Rivin Dec 10 '13 at 22:44
@ABC Yes, I need to actually learn the proof myself. – sjfrei Dec 10 '13 at 23:07
Interesting. RHS is of course a coefficient of $(1+t)^{2m}$ and LHS looks almost like trinomial expansion... – Grigory M Dec 11 '13 at 14:21
I wonder if there is a short proof using the fact that both sides are polynomials in $m$ of deg $2n$ that are both zero in $m=0,1,\ldots,n-1$ and are equal for $m=n$... – Grigory M Jan 5 '15 at 14:52

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 brcause $(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

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:

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.

-
What if being $F(n,k)$ a hypergeometric term in both $n$ and $k$ the last line ratsimp(lhs-rhs); isn't equal 0? – rafaeldf May 29 '15 at 5:01
Depending on what your F(n,k) is, sometimes more rewriting than that by ratsimp is necessary so that maxima can recognize two expressions (lhs and rhs) as equal. And check sols, perhaps it's empty... – ccorn May 29 '15 at 17:59
Thanks for your comment, but I have this $F(n,k) := \frac{1}{4^k} \binom{2k}{k} \binom{n-1+k}{k}$ for which lhs and rhs aren't equal :-/. What is wrong here if $F(n,k)$ is a proper hypergeometric term? – rafaeldf May 29 '15 at 18:57
With the detailed maxima steps as described in the answer (with only $F(n,k)$ adapted to your problem), I get $0$, everything OK here. Furthermore, $R(n,k) = \frac{2k^2}{n}$ and $a = [-2n, 2n+1]$. – ccorn May 29 '15 at 19:33
I notice however that Fk (which holds the rational expression for $\frac{F(n,k+1)}{F(n,k)}$) could be simplified further by cancelling a common $(k+1)$. Perhaps it helps you to wrap an additional ratsimp in the definition of Fk, that is: define (Fk(n,k), ratsimp(factcomb(makefact(F(n,k+1)/F(n,k))))), sumsplitfact:false; -- however, my version of maxima can do without that. – ccorn May 29 '15 at 20:03

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.

-

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|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{m+k} \; dz.$$

This gives the following integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \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|=\epsilon} \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|=\epsilon} \frac{(1+z)^{m-1/2}}{z^{2n+1}} \sum_{k=0}^n {2n+1\choose 2k+1} \sqrt{1+z}^{2k+1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1/2}}{2z^{2n+1}} \left((\sqrt{1+z}+1)^{2n+1} - (\sqrt{1+z}-1)^{2n+1})\right) \; dz.$$

By way of ensuring analyticity of the square root we now instantiate $\epsilon$ to $1/2$ to get $$\frac{1}{2\pi i} \int_{|z|=1/2} \frac{(1+z)^{m-1/2}}{2z^{2n+1}} \left((\sqrt{1+z}+1)^{2n+1} - (\sqrt{1+z}-1)^{2n+1})\right) \; dz.$$

Now put $1+z = w^2$ so that $dz = 2w\; dw$ and the integral becomes $$\frac{1}{2\pi i} \int_{|w-1|=\sqrt{3/2}-1} \frac{w^{2m-1}}{(w^2-1)^{2n+1}} \left((w+1)^{2n+1} - (w-1)^{2n+1})\right) \; w \; dw.$$

This is $$\frac{1}{2\pi i} \int_{|w-1|=\sqrt{3/2}-1} 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}] (w-1+1)^{2m} = {2m\choose 2n}.$$

The second term is analytic on and inside the circle that $w$ traces round the value $1$ and does not contribute anything. This concludes the argument.

Remark. Actually $w$ does not quite trace the circle $\gamma$ used in the integral in $w$ but there is a continuous deformation of the image of the circle $|z|=1$ to that circle $\gamma$.

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

-