How does $n!^2$ divide $(2n)!$?

Question

How can I show that $(n!)^2$ divides $(2n)!$, where $n$ is a natural number?

So far I've noticed that we can rewrite $\dfrac{(2n)!}{(n)!^2}$ as a combination and we know that combinations are always natural, but is there an elegant way that makes more use of divisibility?

Answer 1

Consider the fraction $$\frac{(2n)!}{(n!)^2}$$

It suffices to show that this is an integer. You may recognize the expression as the binomial coefficient

$$\binom{2n}{n}$$

All binomial coefficients are integers, and so, a fortiori, this one is as well. As for why all binomial coefficients are integers, the combinatorial interpretation of a binomial coefficient provides a good intuition.

If this isn't satisfying, I've included a bit of a more directly intuitive approach below.

---

Since $(2n)! = n! \cdot (n+1) \cdot (n+2) \cdots (2n)$, your original expression can be rewritten

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

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

Intuitively, why must every integer included in $n!$ have a multiple appear in the product $(n+1) \cdot (n+2) \cdots (2n)$?

Answer 2

Put any prime $p$ and let $k$ and $\ell$ be the greatest positive integers such that $p^k|(n!)^2$ and $p^\ell|(2n)!$. Then using this \begin{align} k&=2\left(\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\left\lfloor\frac n{p^3}\right\rfloor+\dots\right)\\ &=2\left\lfloor\frac np\right\rfloor+2\left\lfloor\frac n{p^2}\right\rfloor+2\left\lfloor\frac n{p^3}\right\rfloor+\dots\\ &\le \left\lfloor\frac {2n}p\right\rfloor+\left\lfloor\frac {2n}{p^2}\right\rfloor+\left\lfloor\frac {2n}{p^3}\right\rfloor+\dots\\ &=\ell. \end{align} It follows that $p^k|p^\ell$ which implies what you wanted.