1
$\begingroup$

I'm working through Spivak's Calculus and a question asks to verify that sequence $$\lim_{n \to \infty} \frac{n!}{n^{n}} = 0$$.

I've been given the hint that $n! = n(n-1)\dots k!$ for $k < n$, in particular for $k < \frac{n}{2}$.

I didn't succeed in getting a formal solution, but I have access to the solution manual and they did the following:

$$\frac{n!}{n^{n}} = \frac{n(n-1)\dots(\frac{n}{2})!}{n^{\frac{n}{2}}n^{\frac{n}{2}}} \leq \frac{(\frac{n}{2})!}{n^{\frac{n}{2}}} \leq \bigg(\frac{1}{2}\bigg)^{\frac{n}{2}}$$.

I have a few issues with the solution:

1) How is $n(n-1)\dots(\frac{n}{2})! < (\frac{n}{2})!$ ? This makes no sense to me considering that the left side is a larger factorial.

2) How does the relationship $$\frac{(\frac{n}{2})!}{n^{\frac{n}{2}}} \leq \bigg(\frac{1}{2}\bigg)^{\frac{n}{2}}$$ actually come about ?. I agree with it in theory, and I've seen similar expressions in previous work, but I haven't formally encountered this in the text (particularly with treating the factorial). There is probably a similar version to this somewhere on the site that I could look at and attempt to prove.

EDIT

I had forgotten to mention that I had rewritten the expression as

$$\frac{n(n-1)(n-2)\dots(n-k) \dots 1}{n \times n \times n \dots \times n} = \frac{n-1}{n} \frac{n-2}{n} \dots \frac{1}{n}$$

and if I took the limit as $n \to \infty$ for each term I could get $0$, but I felt that this was not the right thing to do and if there was a more formal approach.

$\endgroup$
2
  • 2
    $\begingroup$ That seems far too complicated. It should be clear that $0 \le \dfrac{n!}{n^n} \le \dfrac 1n$ for all $n$. $\endgroup$ – Umberto P. Sep 30 '20 at 23:48
  • $\begingroup$ @Umberto Presumably we also want to know about summability of the sequence. ;) $\endgroup$ – Pedro Tamaroff Oct 1 '20 at 9:37
4
$\begingroup$

It’s easiest to see what’s going on in that calculation when $n$ is even. Suppose that $n=2m$. Then

$$\frac{n(n-1)\ldots(m+1)}{n^m}=\frac{n}n\cdot\frac{n-1}n\cdot\ldots\cdot\frac{m+1}n\le 1\,,$$

so

$$\frac{n!}{n^n}=\frac{n(n-1)\ldots(m+1)m!}{n^mn^m}\le\frac{m!}{n^m}\,.$$

And

$$\frac{m!}{n^m}=\frac{m}n\cdot\frac{m-1}n\cdot\ldots\cdot\frac1n\le\left(\frac12\right)^m\,,$$

because $\frac{k}n\le\frac12$ for $k=1,2,\ldots,m$.

If $n=2m+1$, you can write

$$\frac{n!}{n^n}=\frac{n(n-1)\ldots(m+1)}{n^{m+1}}\cdot\frac{m!}{n^m}\le\frac{m!}{n^m}\le\left(\frac12\right)^m$$

and use the same reasoning.

$\endgroup$
2
  • $\begingroup$ hmmm very interesting. also interesting how the hint was given in the most compact way possible because there was so much to be able to extract from it. This is very clear, thanks again for your expertise. $\endgroup$ – dc3rd Sep 30 '20 at 23:37
  • 1
    $\begingroup$ @dc3rd: You’re very welcome. $\endgroup$ – Brian M. Scott Sep 30 '20 at 23:43
1
$\begingroup$

Observe that \begin{align} \frac{n!}{n^n} =&\exp(\log n!-\log n^n)\\ =&\exp\left(\sum_{j=1}^n(\log j-\log n)\right)\\ =&\exp\left(\sum_{j=1}^n\log\frac jn\right)\\ =&\exp\left(n\sum_{j=1}^n\frac1n\log\frac jn\right)\\ \end{align} and since $$ \sum_{j=1}^n\frac1n\log\frac jn\longrightarrow\int_0^1\log x dx<0 $$ you can conclude.

$\endgroup$
1
  • 1
    $\begingroup$ This gives another method, but doesn’t answer the question posed by the OP. $\endgroup$ – Pedro Tamaroff Oct 1 '20 at 0:03
1
$\begingroup$

A different way $$ \frac{n!}{n^{n}} = \frac{1}{n}\frac{2}{n}\cdots\frac{n-1}{n}\frac{n}{n} $$ Now for every positive number $k < n$ we have that $$ \frac{n - k}{n} \le \frac{n-1}{n} = q_n < 1 $$ It is clear that for every $n$ and every power of $q_n$ we have $q^m_n < 1$. It folows that $$ \frac{n!}{n^{n}} = \frac{1}{n}\frac{2}{n}\cdots\frac{n-1}{n}\frac{n}{n} \le \frac{1}{n}\ \underbrace{q_n \cdots q_n}_{n-2 \text{ factor}} \ \frac{n}{n} = \frac{1}{n}\ q_n^{n-2} < \frac{1}{n}\ $$ Take the limits.

$\endgroup$
0

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.