Show that $m! (n − m)!$ divides $n!$ for all $m$, $n \in \Bbb{N}$ with $m \leq n$.

Question

I am studying Analysis by Amann and Escher by my own I am stuck at this exercise:

Show that $m! (n − m)!$ divides $n!$ for all $m$, $n\in\Bbb{N}$ with $m\leq n$. (Hint: $(n+1)!=n!(n+1−m)+n!m$.)

Thanks in advance

Answer 1

A combinatorial-like proof (fill in details): the number of subsets with $\;m\;$ elements of a set with $\;n\;$ elements, $\;n\ge m\;$ , is given by

$$\binom nm:=\frac{n!}{m!(n-m)!}$$

As the above number is always an integer, the claim follows.

If you want a more algebraic proof, just play a little with the above expression and read carefully Alex's comment.

Answer 2

If you want to use the hint, use induction. It is trivial to check that the statement is true for $n=1$. Suppose it is true for $n$ and for every $m\leq n$. Now suppose $m\leq n+1$. Then \[ \frac{(n+1)!}{m!(n+1-m)!}=\frac{n!(n+1-m)+n!m}{m!(n+1-m)!}=\frac{n!}{(n-m)!m!}+\frac{n!}{(m-1)!(n+1-m)!} \] By the induction hypothesis each term on the right hand side is an integer, so we are done.

Answer 3

Take any prime number $p$ and observe that within $$1 \cdot 2 \cdot 3 \cdot \ldots \cdot k$$ it is used exactly $$ \left\lfloor \frac{k}{p} \right\rfloor +\left\lfloor \frac{k}{p^2} \right\rfloor +\left\lfloor \frac{k}{p^3} \right\rfloor +\ldots $$ times (this series becomes zero after $\log_p k$ steps).

So to prove your theorem we need to show that

$$ \left\lfloor \frac{n}{p} \right\rfloor +\left\lfloor \frac{n}{p^2} \right\rfloor +\left\lfloor \frac{n}{p^3} \right\rfloor +\ldots \geq \left\lfloor \frac{m}{p} \right\rfloor +\left\lfloor \frac{m}{p^2} \right\rfloor +\left\lfloor \frac{m}{p^3} \right\rfloor +\ldots + \left\lfloor \frac{n-m}{p} \right\rfloor +\left\lfloor \frac{n-m}{p^2} \right\rfloor +\ldots $$ which is easy to see when split into multiple similar parts: $$ \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor\frac{m}{p^i}+\frac{n-m}{p^i}\right\rfloor \geq \left\lfloor \frac{m}{p^i} \right\rfloor + \left\lfloor \frac{n-m}{p^i} \right\rfloor$$ because $\lfloor a+b\rfloor \geq \lfloor a \rfloor + \lfloor b \rfloor$ for any real numbers $a$ and $b$.

I hope this helps $\ddot\smile$