# Proving ${ 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!}$

How to prove this binomial identity :

$${ 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!}$$

The left hand side arises while solving a standard binomial problem the right hand side is given in the solution , I checked using induction that this is true but I am inquisitive to prove it in a rather general way.

EDIT: I have gone through all of the answers posted here,I particularly liked Isaac♦ answers after which it was not much difficult for me to figure out something i would rather say an easy and straight algebraic proof, I am posting it here if somebody needs in future :

$${ 2n \choose n } = \frac{(2n)!}{n! \cdot n!}$$

$$= \frac{ 1 \cdot 2 \cdot 3 \cdots n \cdot (n+1) \cdots (2n-1)\cdot (2n) }{n! \cdot n!}$$

$$= \frac{ [1 \cdot 3 \cdot 5 \cdots (2n-1)] \cdot [2 \cdot 4 \cdot 6 \cdots (2n)]}{n! \cdot n!}$$

$$= \frac{ [1 \cdot 3 \cdot 5 \cdots (2n-1)] \cdot [(2.1) \cdot (2.2) \cdot (2.3) \cdots (2.n)]}{n! \cdot n!}$$

$$= \frac{ [1 \cdot 3 \cdot 5 \cdots (2n-1)] \cdot [ 2^n \cdot (n)! ]}{n! \cdot n!}$$

$$= 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!}$$

Your original identity, ${ 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!}$, can be rewritten (by multiplying both sides by $(n!)^2$) as $(2n)!=2^n\cdot 1\cdot 3\cdot 5\cdots (2n-1)\cdot n!$. Now, $2^n\cdot 1\cdot 3\cdot 5\cdots (2n-1)\cdot n!=$ $1\cdot 3\cdot 5\cdots (2n-1)\cdot 2\cdot 4\cdot 6\cdots 2n=$ $1\cdot 2\cdot 3\cdots (2n-1)(2n)=(2n)!$.

• +1 and accepted for showing me the algebraic way, really appreciated :) – Quixotic Oct 25 '10 at 8:44

If you have proved it via induction, the you have proved it. I don't know what you mean by "in a rather general way".

But note that $$1\cdot3\cdot5\cdot\cdots\cdot(2n-1)$$ is just crying out to be rewritten as $$\frac{1\cdot2\cdot3\cdot\cdots\cdot(2n)} {2\cdot4\cdot6\cdot\cdots\cdot(2n)}.$$

• Yes, but so I have to cram this for future ? By in general way I mean algebraic proof since it easier for me to remember :) Also it is not much possible to proof via induction under exam constraints :) – Quixotic Oct 25 '10 at 8:36
• @Debanjan: "Not possible"? Certainly, if you've practiced enough, you should be able to write down an inductive proof in the same amount of time as writing an "algebraic" proof... – J. M. is a poor mathematician Oct 25 '10 at 10:36

Here's the more general way that you seek. The LHS and RHS are both products of rational functions of $\rm\:n\:$, i.e. they satisfy $\rm\ f(n+1) = r(n)\ f(n)\$ for some rational function $\rm r(n)\:$. To test whether two such functions are equal you need only test that they have the same value of $\rm\ r(n) = f(n+1)/f(n)\$ and the same initial condition $\rm\: f(0)$.$\$ For the above it's trivial: $\rm\ f(0) = 1\:$ and the common value of $\rm\ r(n)\$ is

$\rm\quad\quad\quad\displaystyle f(n)\ \ =\ \ {2n \choose n}\ \: =\: \ \frac{(2n)!}{n!^2}\ \ \Rightarrow\ \frac{f(n+1)}{f(n)}\ =\ \frac{2\:(n+1)\:(2n+1)}{\ (n+1)\ (n+1)}$

$\rm\quad\quad\quad\displaystyle f(n)\ =\ 2^n \frac{ 1 \cdot 3 \cdots (2n-1)}{n!} \ \Rightarrow\ \frac{f(n+1)}{f(n)}\ =\ \frac{2\ (2n+1)}{n+1}$

Notice that this method is completely algorithmic - it requires no insight whatsoever. In essence one is employing the uniqueness theorem for first order difference equations (recurrences) to prove an equality by simply checking that both sides satisfy the same difference / differential equation and initial conditions. Such techniques generalize to much wider classes of multivariate mixed differential - difference equations, e.g. holonomic functions. For some further examples of this powerful technique see my post here.

• @Bill This is a really interesting technique. In fact it reminds me of the way in which Tom Apostol proves the formula for the volume of an n-dimensional sphere in his book on multivariable calculus. He first shows that the two things he wants to prove equal satisfy the same recurrence relation and then that they both satisfy the same initial conditions, so they must be the same. – Adrián Barquero Oct 26 '10 at 1:11
• Really nice! What is the name for such a set of techniques? (including the slight variation you used in math.stackexchange.com/questions/3502/…) – Robert Smith Oct 26 '10 at 3:45
• @Bill Isn't that the method of A=B? – Yuval Filmus Oct 26 '10 at 4:57
• @Robert: I don't think there is any standard name. Some cases are specializations of various integral transforms, Fourier, Mellin, Z, etc. Some include such methods in the catch-all phrases, generating function, operator algebra, etc. Googling "holonomic Zeilberger" should yield a good entry point into the literature. – Bill Dubuque Oct 26 '10 at 16:33
• @Yuval: Probably they are mentioned in the book A=B. But these techniques are very, very old. They've come back into fashion recently primarily because of their utility for effective computation. Since I learned about them long before A=B was published (when Gosper and I were were working on effective theories of special functions for Macsyma), I've never had the need to read A=B. But I do seem to recall that Zeilberger has mentioned such topics in some of his papers so they are probably also discussed in A=B. – Bill Dubuque Oct 26 '10 at 16:45

Multiply right side by $\frac{n!}{n!}$, and distribute the $2^n$.

Here's an enumerative proof. Consider the following procedure for dividing a set $S$ of size $2n$ into two sets $A,B$ of size $n$. The procedure proceeds in $n$ rounds. We start with $A,B$ empty. In each round, let $m = \min S$ and pick some $x \in S \setminus m$. Now decide whether to put $m$ in $A$ and $x$ in $B$, or to put $m$ in $B$ and $x$ in $A$. Remove both $m,x$ from $S$.

Clearly, the procedure ends with the required partition, and requires $(2n-1)(2)(2n-3)(2)\cdots(1)(2)$ choices. Furthermore, I claim that each partition can be generated in $n!$ ways. Indeed, at each round, either $m \in A$ or $m \in B$; suppose wlog that $m \in A$. This forces our second choice, and for our force choice, we can choose an arbitrary member of $B$. So our total degrees of freedom are $(n)(n-1)\cdots(1)$.