2
$\begingroup$

In a question I am asked to find $\lim_{n \to \infty}\frac{n!}{n^n}$ using the sandwich theorem.

I can see that the limit is going to be 0 as $\frac{n!}{n^n}$ can be written as $\frac{n}{n}*\frac{n-1}{n}*\frac{n-2}{n}*...*\frac{1}{n}$ but I cannot see how I can find two sequences which 'squeeze' the given function.

Any help would be greatly appreciated!

$\endgroup$
9
$\begingroup$

We have $$0 < \frac{n!}{n^n} = \frac{n}{n} \frac{n-1}{n} \cdots \frac{1}{n} \leqslant 1 \cdot 1 \cdots 1 \cdot \frac{1}{n} = \frac{1}{n}$$ since the denominator of each term is bigger than the numerator. Now squeeze.

$\endgroup$
  • 1
    $\begingroup$ Thanks very much! I hate how these questions are so simple once you see a possible solution! $\endgroup$ – P Collier Jul 30 '16 at 16:50
2
$\begingroup$

An idea: You can write: $n! = n(n-1)(n-2)\dots\frac{n}{2}\dots 1$. From there, $0\leq n! \leq n^{\frac{n}{2}-1}\cdot \left(\frac{n}{2}\right)^{\frac{n}{2}}$.

Can you conclude from there? (As a small remark: this will give you that the convergence to $0$ is exponentially fast.)

(Note that for convenience, i assumed above $n$ was even; if $n$ is odd, basically the same thing will work. You can add floors or ceilings to handle the two cases at once.)

$\endgroup$
  • $\begingroup$ This is most likely not in your toolbox yet, but if you are interested in the exact rate of convergence, Stirling's approximation is the right "hammer." Namely, $\frac{n!}{n^n}$ behaves exactly like ${\sqrt{2\pi n}}e^{-n}$ when $n\to\infty$. $\endgroup$ – Clement C. Jul 30 '16 at 16:51
  • $\begingroup$ Thanks for your answer! and yes I haven't come across that but I'll have a look now :) $\endgroup$ – P Collier Jul 30 '16 at 16:53
  • $\begingroup$ You're welcome! Zain Patel's answer is simpler, if you don't care about showing that it goes to zero "very fast." (I would also encourage you to keep Stirling's in mind, for later -- it is a useful string to have to one's bow.) $\endgroup$ – Clement C. Jul 30 '16 at 16:54
  • $\begingroup$ @ClementC. I posted a solution that refers to another solution I posted a few days ago in which I used the trapezoidal rule to show the behavior of $n!$ for large $n$. I did not develop the $\sqrt{2\pi}$ part which is, I believe, the more challenging piece of Stirling's formula. $\endgroup$ – Mark Viola Jul 30 '16 at 17:09
  • $\begingroup$ Yes, pinpointing the constant is the "hardest" bit (without the constant, it becomes a much simpler exercise of real analysis). $\endgroup$ – Clement C. Jul 30 '16 at 17:20
2
$\begingroup$

PRIMER:

In THIS ANSWER, I showed using only straightforward arithmetic along with the Trapezoidal Rule that

$$n!=\sqrt{n}\left(\frac ne\right)^n\,O\left(1\right) \tag 1$$

Therefore, we see immediately that

$$\lim_{n\to \infty}\frac{n!}{n^n}=0$$

as expected!

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