Here's a simple fact:

The simplest of the proofs is combinatorial: after all, the binomial coefficient {n+m \choose m} = \frac{(n+m)!}{n!m!} is an integer, so that the product (m+1)(m+2)\cdot...\cdot(m+n) is divisible by n!.

As a particular case, (2n)! is divisible by (n!)^{2}. But, to complicate things, a stronger assertion is true:

I met this problem in a Russian collection of olympiad problems as an assertion that \frac{(2n)!}{(n!)^{2}} is divisible by n+1.

For a proof, consider another binomial coefficient (and, hence, an integer) {{2n} \choose {n+1}} = \frac{(2n)!}{(n-1)!(n+1)!} .

Let A = \frac{(2n)!}{(n!)^{2}} and B = \frac{(2n)!}{(n-1)!(n+1)!}. Then

This implies that n+1 divides An, but, since n+1 and n are mutually prime, it follows by Euclid's Lemma (*Elements*, VII.30) that n+1 divides A.

Incidently, quantity {\frac{1}{n+1}}{2n \choose {n}} is well known in combinatorics as the *Catalan number*. Catalan numbers arise in a multitude of counting scenarios.

E. Catalan proved more general results [Dickson, p. 265-267] . For example,

is integer, provided m and n are mutually prime. This is a direct generalization of the above. Also

is integer for integer n and m.

Here is another one [Nagell, p. 124] :

**References**

- L. E. Dickson,
*History of the Theory of Numbers*, v 1, Dover, 2005 - T. Nagell,
*Introduction to Number Theory*, Chelsea, 1981