How to prove $ \frac{m!}{n!} \geq n^{m-n} $

Question

How to prove the following:

$$ \frac{m!}{n!} \geq n^{m-n} $$

In my book it's written: "easy to prove by separately considering the cases $m \geq n$ and $m<n$).

I tried using the bounds of Stirling and I got:

$$ \frac{m!}{n!} \geq \frac{\sqrt{2\pi}}{e} n^{m-n} $$

But this bound is not tight as the first since $\frac{\sqrt{2\pi}}{e}\approx 0.92$

Thanks!

Answer 1

Stirling approximation is not useful here. The definition of factorial is all we need.

Note that if $m\geq n$ then $$m!=\underbrace{m\cdot (m-1)\cdots (n+1)}_{\text{$m-n$ factors each one $>n$}}\cdot n!$$ On the other hand if $n>m$ then $$n!=\underbrace{n\cdot (n-1)\cdots (m+1)}_{\text{$n-m$ factors each one $\leq n$}}\cdot m!$$ Can you take it from here?

Answer 2

Hint:

For $m \ge n$, $$\frac{m!}{n!} = m\times(m-1)\times\cdots\times(n+1) \ge n\times n \times \cdots n=n^{m-n}$$ What happens for $m \le n$? $$\frac{m!}{n!} = \frac{1}{n\times(n-1)\times\cdots\times(m+1)} \ge ?$$

Answer 3

For $m \ge n$ $$\frac{m!}{n!}=(n+1) \cdot (n+2) \cdots (m-1) \cdot m \ge n \cdot n \cdots n = n^{m-n}$$

Answer 4

No need for Stirling here, elementary computationw work way better.

When $n \leq m$, $m!/n!$ is a product of $n-m$ integers, all greater than $n$, thus $m! \geq n^{m-n}n!$.

When $n > m$, $m!/n!$ is a product of reciprocals of $n-m$ integers all $\leq n$, so the product is $\geq (1/n)^{n-m}=n^{m-n}$.