Binomial Identity $\sum\binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$

Question

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!

Answer 1

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

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.

Answer 2

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.

Answer 3

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.