4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Closing this question? I don't understand... $\endgroup$ – Robert Z Jan 25 at 17:47
10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I upvoted you Robert! Thanks! $\endgroup$ – Felipe Jan 25 at 17:55
  • $\begingroup$ Thanks. You are welcome! $\endgroup$ – Robert Z Jan 25 at 17:57
4
$\begingroup$

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}$$

$\endgroup$
3
$\begingroup$

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 ?$$

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.