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!

  • $\begingroup$ 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. $\endgroup$
    – OR.
    Dec 10, 2013 at 22:41
  • $\begingroup$ Mathematica confirms immediately. $\endgroup$
    – Igor Rivin
    Dec 10, 2013 at 22:44
  • 1
    $\begingroup$ @ABC Yes, I need to actually learn the proof myself. $\endgroup$
    – sjfrei
    Dec 10, 2013 at 23:07
  • 1
    $\begingroup$ Interesting. RHS is of course a coefficient of $(1+t)^{2m}$ and LHS looks almost like trinomial expansion... $\endgroup$
    – Grigory M
    Dec 11, 2013 at 14:21
  • $\begingroup$ 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$... $\endgroup$
    – Grigory M
    Jan 5, 2015 at 14:52

3 Answers 3


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


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);

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:


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.

  • $\begingroup$ What if being $F(n,k)$ a hypergeometric term in both $n$ and $k$ the last line ratsimp(lhs-rhs); isn't equal 0? $\endgroup$
    – rafaeldf
    May 29, 2015 at 5:01
  • 1
    $\begingroup$ 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... $\endgroup$
    – ccorn
    May 29, 2015 at 17:59
  • $\begingroup$ 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? $\endgroup$
    – rafaeldf
    May 29, 2015 at 18:57
  • $\begingroup$ 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]$. $\endgroup$
    – ccorn
    May 29, 2015 at 19:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – ccorn
    May 29, 2015 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|=\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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .