Prove the identity


This is reminiscent of the identity $\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}$, which has a nice combinatorial interpretation of choosing $n$ from $2n$ objects. But the identity in question is not easily related to a combinatorial interpretation. Also, for an induction proof, it is not clear how to relate the identity with $n$ to $n+1$.


marked as duplicate by Petite Etincelle, Ross Millikan algebra-precalculus Nov 12 '14 at 22:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Should those combinations be 2n-2 choose n-1, instead of choose 2n-1? And 2n-4 choose n-2, not choose 2n-2? $\endgroup$ – Simon S Nov 12 '14 at 21:41
  • $\begingroup$ @SimonS You're right. $\endgroup$ – Dexter Nov 12 '14 at 21:43
  • $\begingroup$ Perhaps, the hypergeometric distribution helps. $\endgroup$ – Peter Nov 12 '14 at 21:45
  • 2
    $\begingroup$ This is a simple convolution which may be evaluated with $$\sum_{k\ge 0}{2k\choose k} z^k = \frac{1}{\sqrt{1-4z}}$$ which in turn can be proved by Lagrange inversion if desired. $\endgroup$ – Marko Riedel Nov 12 '14 at 21:54

By way of enrichment here is another algebraic proof using basic complex variables. As I pointed out in the comment this identity is very simple using a convolution, so what follows should be considered a learning exercise.

We seek to compute $$\sum_{k=0}^n {2k\choose k} {2n-2k\choose n-k}.$$

Introduce the integral representation $${2n-2k\choose n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-2k}}{z^{n-k+1}} \; dz.$$

We use this to obtain an integral for the sum. Note that when $k>n$ the pole at zero disappears which means that the integral is zero. Therefore we may extend the sum to infinity, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sum_{k\ge 0} {2k\choose k} \frac{z^k}{(1+z)^{2k}}\; dz.$$

Recall that $$\sum_{k\ge 0} {2k\choose k} w^k = \frac{1}{\sqrt{1-4w}}$$ so this becomes $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \frac{1}{\sqrt{1-4z/(1+z)^2}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \frac{1+z}{\sqrt{(1+z)^2-4z}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \frac{1}{1-z} \; dz.$$

Extracting coefficients we get $$\sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 2^{2n} = 4^n.$$

Apparently this method is due to Egorychev.

Addendum. The Lagrange inversion proof goes like this. We seek to compute $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{1}{\sqrt{1-4z}} \; dz.$$

Put $1-4z = w^2$ so that $z= \frac{1}{4} - \frac{1}{4} w^2$ and $dz = -\frac{1}{2} w \; dw$ to get $$-\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^{k+1}}{(1-w^2)^{k+1}} \frac{1}{w} \frac{1}{2} w \; dw \\ = -\frac{2^{2k+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(1-w)^{k+1}} \frac{1}{(1+w)^{k+1}} \; dw \\ = -\frac{2^{2k+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(1-w)^{k+1}} \frac{1}{(2+w-1)^{k+1}} \; dw \\ = -\frac{2^k}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(1-w)^{k+1}} \frac{1}{(1+(w-1)/2)^{k+1}} \; dw \\ = -\frac{2^k (-1)^{k+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w-1)^{k+1}} \frac{1}{(1+(w-1)/2)^{k+1}} \; dw.$$

Extracting coefficients we obtain $$- 2^k (-1)^{k+1} {k+k\choose k} \frac{(-1)^k}{2^k} = {2k\choose k}.$$

It is not difficult to see that in the above substitution the image of a small radius counterclockwise circle around the origin in the $z$ plane is a small radius circle around $w=1$ also traversed counterclockwise.

A similar calculation may be found at this MSE link.


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