# Prove that: $\big(m+n\big)!\over m!n!$ is a natural number?

Prove that:

(I can't prove without binomial coefficient.)

$$\big(m+n\big)!\over m!n!$$ is a natural number

you can use : formula for the largest power of a prime dividing a factorial $$n!=p_1^\alpha* p_2^\beta* ...$$ $$\alpha= \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor+...$$

-
Well, if you use that formula, this boils down to an elementary $\lfloor x+y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$. Did you try to prove that? – Alexander Shamov Nov 29 '12 at 15:51

Let $p$ be a prime. Write $\nu_p(k)$ for the exponent of $p$ in the prime decomposition of $k$. We have for $i \in \mathbb N$: $$\frac{n+m}{p^i} = \frac n{p^i} + \frac{m}{p^i}$$ so, making the right hand side possibly smaller $$\frac{n+m}{p^i} \ge \left\lfloor\frac n{p^i}\right\rfloor + \left\lfloor\frac m{p^i}\right\rfloor$$ Now the right hand side is an integer, hence by definition of the floor function $$\left\lfloor \frac{n+m}{p^i}\right\rfloor \ge \left\lfloor\frac n{p^i}\right\rfloor + \left\lfloor\frac m{p^i}\right\rfloor$$ This gives \begin{align*} \nu_p(n!m!) &= \nu_p(n!) + \nu_p(m!)\\ &= \sum_{i=1}^\infty \left\lfloor \frac{n}{p^i} \right\rfloor + \sum_{i=1}^\infty \left\lfloor\frac m{p^i}\right\rfloor\\ &\le \sum_{i=1}^\infty \left\lfloor \frac{n+m}{p^i}\right\rfloor \\ &= \nu_p\bigl((n+m)!\bigr) \end{align*} And therefore $$n!m! = \prod_p p^{\nu_p(n!m!)} \biggm| \prod_p p^{\nu_p((n+m)!)} = (n+m)!$$ that is the denominator divides the numerator in $\frac{(n+m)!}{n!m!}$ and so the quotient is an integer.
form very last equation $n!m! = (n+m)!$ ? – Nikita Evseev Nov 29 '12 at 15:53
Note the $|$ ... it is to be read as "divides", as in $2\mid 4$... – martini Nov 29 '12 at 15:53