Show $\frac{(2n)!}{n!\cdot 2^n}$ is an integer for $n$ greater than or equal to $0$ 
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!
 A: 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)$.  
A: 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)$$
A: 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)$.
A: The simplest way is to prove by induction as already shown in another answer. Another way to see why it's an integer is that this is exactly the unique number ways you can pair up all the vertices in a complete graph (also called matching). The number of ways of doing something can't be anything apart from a positive integer.
