Show $\frac{(2n)!}{n!\cdot 2^n}$ is an integer for $n$ greater than or equal to $0$

Question

Show $$\frac{(2n)!}{n!\cdot 2^n}$$ is an integer for $n$ greater than or equal to $0$.

Could anyone please help me with this proving? Thanks!

Answer 1

Induction works.

For inductive step:

$$\frac{(2n+2)!}{(n+1)!\cdot 2^{n+1}}=\frac{(2n)!}{n!\cdot 2^n}\cdot\frac{(2n+1)(2n+2)}{(n+1)\cdot 2}=\frac{(2n)!}{n!\cdot 2^n}\cdot(2n+1)$$

Answer 2

You can see that $n! \cdot 2^n$ is exactly $\prod_{i=1}^n 2i$.

Then any of these (even) number appears in the numerator $(2n)! = \prod_{j=1}^{2n}j$.

Then the division is an integer. It is exactly $\prod_{i=1}^n (2i-1)$.

Answer 3

There are $mn$ people ($m,n$ are nonnegative integers). We want to put them into $n$ groups, each consisting of $m$ people. Let $N$ be the number of ways to do so. If we label the groups, say, groups $1$, $2$, $\ldots$, $n$, there are $n!$ ways for the labeling. Hence, there are $n!\cdot N$ ways to put $mn$ people into $n$ labeled groups.

Now, from $mn$ people, we can choose in $\binom{mn}{m}$ ways $m$ persons and put them into group $1$. For $k=2,3,\ldots,n$, we can place $m$ persons from the remaining $mn-m(k-1)$ people into group $k$ in $\binom{mn-m(k-1)}{m}$ ways. Therefore, we can perform this task (with labeled groups) in $\binom{mn}{m}\binom{mn-m}{m}\binom{mn-2m}{m}\cdots\binom{2m}{m}\binom{m}{m}=\frac{(mn)!}{(m!)^n}$ ways.

That is, $n!\cdot N=\frac{(mn)!}{(m!)^n}$. Ergo, $\frac{(mn)!}{(m!)^nn!}=N$ is an integer. Your question is a particular case where $m=2$.

In parallel to Laurent's and mathlove's arguments, we shall also prove that $\frac{(mn)!}{(m!)^nn!}=N=\prod_{k=1}^n\binom{mk-1}{m-1}$. Consider again $mn$ people which will be placed into $n$ (unlabeled) groups, each having $m$ members. Pick a person. He has to be in a group. Therefore, this group needs $m-1$ other members which can be chosen from the remaining $mn-1$ people in $\binom{mn-1}{m-1}$ ways. For $k=2,3,\ldots,n$, we already have $k-1$ groups, and so we pick one person from $mn-m(k-1)$ people. Put this person into a group, and choose $m-1$ people to be in the same group from the remaining pool of $mn-m(k-1)-1$ people in $\binom{mn-m(k-1)-1}{m-1}$ ways. This shows $N=\binom{mn-1}{m-1}\binom{mn-n-1}{m-1}\cdots\binom{2m-3}{m-1}\binom{m-1}{m-1}=\prod_{k=1}^n\binom{mk-1}{m-1}$. When $k=2$, we retrieve Laurent's formula: $\frac{(2n)!}{2^nn!}=\prod_{k=1}^n(2k-1)$.