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

Question

Prove: $$ \frac{1\times 3\times 5\times \cdots \times (2n - 1)}{2^n (n + 1)!} \times 4^n = \frac{1}{n+1} \binom{2n}{n} $$

-Sorry I don't know how to do choose notation in stack exchange.

I'm having a bit of trouble proving this, I tried to prove this by induction and would get stuck. Any help is appreciated in advance.

Answer 1

By multiplying both numerator and denominator by $\;2\cdot 4\cdot 6 \cdot \ldots \cdot (2n)=2^nn!$ we get \begin{align} \frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{2^n(n+1)!}&=\frac{1\cdot \color{red}{2}\cdot 3\cdot \color{red}{4}\cdot 5\cdot \color{red}{6}\cdot \ldots \cdot (2n-1)\cdot\color{red}{2n}}{2^n(n+1)!\cdot \color{red}{2^nn!}}\\ &=\frac{1}{4^n(n+1)}\cdot\frac{(2n)!}{n!\cdot n!}\\ &=\color{blue}{\frac{1}{4^n(n+1)}{2n \choose n}} \end{align}

Then $$\boxed{\color{blue}{4^n\left[\frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{2^n(n+1)!}\right]=\frac{1}{n+1}{2n \choose n}}}$$

Answer 2

You can also prove it combinatorially. First multiply by $(n+1)!$ and simplify a little to get the equivalent identity

$$1\cdot3\cdot5\cdot\ldots\cdot(2n-1)\cdot 2^n=n!\binom{2n}n\;.\tag{1}$$

I claim that each side of $(1)$ is the number of ways to divide a pool of $2n$ chess players into $n$ pairs and assign one member of each pair to play the white pieces.

• There are $2n-1$ players who can be paired with the youngest player. Once that pair has been formed, the youngest player remaining can be paired with any of the other $2n-3$ players who are left. Continuing in this fashion, always forming the next pair by picking an opponent for the youngest remaining player, we end up with $n$ pairs of players, and every set of $n$ pairs can be formed in this way. Thus, there are $1\cdot3\cdot5\cdot\ldots\cdot(2n-1)$ ways to pair up the players. Once the $n$ pairs are formed, we have a two-way choice in each pair as to which player gets the white pieces, so there are $2^n$ ways to make all of those choices. This takes care of the lefthand side of $(1)$.

• Alternatively, we can first choose $n$ of the $2n$ players to play the white pieces in their matches; this can be done in $\binom{2n}n$ ways. We send one of these players to each table. There are then $n!$ different ways to permute the remaining $n$ players amongst the $n$ tables, each of which yields a different set of $n$ pairs. Every pairing and assignment of the white pieces to one member of each pair is obtained in this way, so this takes care of the righthand side of $(1)$.

This establishes $(1)$ and hence the desired identity.