Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  ABC Dec 10 '13 at 22:41
    
Mathematica confirms immediately. –  Igor Rivin Dec 10 '13 at 22:44
1  
@ABC Yes, I need to actually learn the proof myself. –  sjfrei Dec 10 '13 at 23:07
1  
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

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.