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 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.

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|=\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$.