1
$\begingroup$

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

  • 0
    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?2012-11-29

1 Answers 1

5

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.

  • 1
    Note the $|$ ... it is to be read as "divides", as in $2\mid 4$...2012-11-29