Proving that $\frac{(n+m)!}{m!(n-m)!}$ is an integer for $0 \leq m < n$. Experiments using a computer seem to indicate that this is true but I am not sure how to prove it. Any ideas?
 A: Even more is true:
$$ \frac{n!}{m!(n-m)!} = {n \choose m}$$
is an integer, because of the combinatorial interpretation of binomial coefficients. Your number is:
$$ \frac{(n+m)!}{m!(n-m)!} = \frac{n!}{m!(n-m)!} \cdot (n+1) \dots (n+m),$$
hence also an integer.

By the way,  $\frac{1}{m!} \frac{(n+m)!}{m!(n-m)!} =  {n \choose m}  {n+m \choose m}$, so your number also happens to be a multiple of $m!$.

If one does not like to use combinatorics to prove that $ {n \choose m} := \frac{n!}{m!(n-m)!} $ is an integer, one can:


*

*Use induction on $n+m$ and exploit the relation $  {n \choose m} =  {n-1\choose m} +  {n-1 \choose m-1}$ (which is proved by elementary arithmetic). [thanks  Cameron Buie]. Hence, if ${n \choose m} $ are integers for all $n,m \geq 0$ with $n+m < S$, then for $n,m \geq 0$ with$n+m =S$ we have either: a) $n = 0$ and ${n\choose m } = 0 $ or b) $m = 0$ and ${n\choose m } = 1 $ or c) $n,m > 0$ and by induction $  {n \choose m} =  {n-1\choose m} +  {n-1 \choose m-1}$ is a sum of two integers.

*Use 'pure' number theory and exploit the fact that $n!$ is divisible by a prime $p$ exactly in the power $\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \dots$. Hence, it is enough to show that $$\sum_{k} \lfloor n/p^k \rfloor \geq \sum_{k} \lfloor m/p^k \rfloor + \sum_{k} \lfloor (n-m)/p^k \rfloor,$$
which is straightforward. In fact, this method can immediately be applied to the original problem; it suffices to show 
$$\sum_{k} \lfloor (n+m)/p^k \rfloor \geq \sum_{k} \lfloor m/p^k \rfloor + \sum_{k} \lfloor (n-m)/p^k \rfloor,$$
which is easier.

*Use Google or search feature of MSE:
How come $\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}$ is always an integer? ,
Division of Factorials
