2
$\begingroup$

This question already has an answer here:

Using a calculator, I found that $n!$ grows substantially slower than $n^n$ as $n$ tends to infinity. I guess the limit should be $0$. But I don't know how to prove it. In my textbook a hint is given that:

Set $a_n=n!/n^n$ Set $m=[n/2]$(floor function), then $a_n \le (1/2)^m\le(1/2)^{n/2}$. Then by comparing to the geometric progression, the sequence $a_n$ tends to $0$.

I have trouble proving the relationship $a_n \le (1/2)^m\le(1/2)^{n/2}$, (I tried to prove by considering separate cases, that is when $m$ is odd and when it is even) using induction gets me nowhere. Or is there other way to prove this limit? I made some search on web and used Stirling's approximation, but to no avail.

P/S: Although some said that my question is probably duplicate, the main point in my question is understanding and proving the relationship of the inequalities, which I had trouble understanding and was not addressed in the other suggested question(the sequence $(1/n)$ was used as comparison instead of $(1/2)^{n/2}$.)

$\endgroup$

marked as duplicate by Najib Idrissi, N. F. Taussig, muaddib, Batman, Mnifldz Aug 8 '15 at 17:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I can't believe that Stirling's formula is useless here: en.wikipedia.org/wiki/Stirling%27s_approximation $\endgroup$ – Siminore Aug 8 '15 at 15:12
  • $\begingroup$ @Siminore - you can use stirling's formula here, but you have to know how to play with big O terms. $\endgroup$ – Batman Aug 8 '15 at 15:14
  • 1
    $\begingroup$ @Siminore It's not useless at all... You get $n!/n^n \sim \sqrt{2\pi n}e^{-n}$, and so you're reduced to showing $\lim \sqrt{n}e^{-n} = 0$ (which is easy and an even more standard exercise). But really what's the point? The proof is 100x easier than proving Stirling's formula. $\endgroup$ – Najib Idrissi Aug 8 '15 at 15:38
9
$\begingroup$

Hint: $a_n = \frac{n}{n} \frac{n-1}{n} \ldots \frac{3}{n} \frac{2}{n} \frac{1}{n}$.

Each term in the product is at most $1$ (so the first n/2 terms are less than 1 each), and the last $n/2$ terms are less than $\frac{1}{2}$.

So, $a_n \leq (1/2)^\frac{n}{2}$

$\endgroup$
  • $\begingroup$ I'm a huge fan of this method! (+1) $\endgroup$ – Kari Aug 8 '15 at 15:59
  • $\begingroup$ @Khallil, It is sufficient to show that $$0<a_n<\dfrac1n,$$ right? $\endgroup$ – lab bhattacharjee Aug 8 '15 at 16:23
  • $\begingroup$ Why would it be? $\endgroup$ – Kari Aug 8 '15 at 16:58
  • $\begingroup$ @labbhattacharjee - it is. I think theres probably another part of the problem which is to talk about $\sum_{n\geq 0} a_n$ though, where the fact that the $a_n$ is geometrically dominated is important. $\endgroup$ – Batman Aug 8 '15 at 17:36
11
$\begingroup$

Note that $$0 < \frac{n!}{n^n} = \frac{n \times (n - 1) \times \cdots \times 1}{n \times n \times \cdots \times n} = 1 \times \frac{n - 1}{n} \times \cdots \times \frac{1}{n} \leq 1 \times 1 \times \cdots \times \frac{1}{n} = \frac{1}{n}.$$ The answer $0$ follows from the squeeze principle.

$\endgroup$
1
$\begingroup$

Hint: Use the $\{x_n\}$ be sequence of positive real numbers such that $L=\lim \frac {x_{n+1}}{x_n}$ exists. If $L\lt1$, then $\{x_n\}$ converges and $\lim x_n=0$. Now in your case $$\lim \frac {x_{n+1}}{x_n}=\lim \frac {(n+1)!\times n^n}{(n+1)^{n+1}\times n!}\\ =\lim [\frac{n}{n+1}]^n=\lim \frac {1}{(1+\frac{1}{n})^n}=1/e\lt1$$

Now Using above statement we have, $$\lim \frac{n!}{n^n}=0$$

$\endgroup$
1
$\begingroup$

One more way: consider $e^{\log \frac{n!}{n^n}} = e^{\sum_k \log n - n \log n}$. Take bounds on the sum:

$$ \int_{1}^{n} \log x dx < \sum_{k=1}^{n} \log k <1 + \int_{1}^{n} \log x dx $$

and the result follows by the squeeze thm.

$\endgroup$

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