4
$\begingroup$

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!

$\endgroup$
10
$\begingroup$

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)$.

$\endgroup$
7
$\begingroup$

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)$.

$\endgroup$
3
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ The 2n + 1 from the inductive step gives me an integer. But how can I show (n+1) (n+2) ...( 2n) when divided by 2^n gives an integer ? $\endgroup$ – NetUser5y62 Jul 7 '15 at 11:25
  • $\begingroup$ @GuoJinLong: This is induction. We suppose that $\frac{(2n)!}{n!\cdot 2^n}$ is an integer. Then, we know that $\frac{(2n+2)!}{(n+1)!\cdot 2^{n+1}}$ is also an integer. $\endgroup$ – mathlove Jul 7 '15 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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