2
$\begingroup$

"Examine whether the given progressions converge (eventually improperly) and determine their limits where applicable.

(a) $$(a_n)_{n\in\mathbb{N}}:=\frac{n^n}{n!}$$

[...]"

I am having problems getting this homework done as I have no clue about convergency at all. Through Mathematica I know that $\lim\limits_{n\to\infty}a_n=+\infty$ however I don't know how to proove it! During my research I found out that for sufficient big $n$ the inequality $x^n\leq n!\leq n^n$ for $x\in\mathbb{R}$ and $n\in\mathbb{N}$ is true. However this doesn't help me at all. Having a look at our lecture notes I developed the following statement: every $x^n$ with $|x| \geq 1$ diverges as $x^n$ is unbounded and therefore has the improper limit $\lim\limits_{n\to\infty}x^n=+\infty$. Furthermore it seems obvious to me that I need to express the terms in a simpler way, like fractions converging to 0 etc, but I don't know how. Neither some work with the $\varepsilon$-definition of limits in combination with the triangle inequality helped me out. Any suggestions or hints?

Information: This is "Analysis for computer scientist" and therefore we haven't "officially" learned any fancy tricks like L'Hôpital's rule etc. just basic properties of $\mathbb{R}$ and some inequalities as this is an introductory lecture.

$\endgroup$
6
  • 4
    $\begingroup$ Hint: $a_{n+1}/a_n=(1+1/n)^n$, whose limit when $n\to\infty$ should be clear. $\endgroup$
    – Did
    Oct 31, 2011 at 23:29
  • 1
    $\begingroup$ Hint: $a_n=n\prod_{j=2}^n\frac nj$, and since $\frac nj\geq 1$ for $2\leq j\leq n$, we have $a_n\geq n$. $\endgroup$ Oct 31, 2011 at 23:29
  • 3
    $\begingroup$ Hint: $$\frac{n^n}{n!}=\frac{n}{1}\cdot\frac{n}{2}\cdot\frac{n}{3}\cdots\frac{n}{n}$$ The first factor grows without bound, and none of the subsequence ones is ever less than $1$. $\endgroup$ Oct 31, 2011 at 23:30
  • $\begingroup$ If you are also convinced that for big $n$, one has $(n+1)!\leq n!$, you have done. $\endgroup$ Oct 31, 2011 at 23:33
  • $\begingroup$ I just want encourage you to keep at it and try to master this material. As a computer scientist, you will find the ability to understand limits such as this one very useful in analyzing the efficiency of algorithms. $\endgroup$ Oct 31, 2011 at 23:55

2 Answers 2

5
$\begingroup$

HINT: $$\begin{align*} \frac{n^n}{n!}&=\frac{n}{n}\cdot\frac{n}{n-1}\cdot\frac{n}{n-2}\cdot\dots\cdot\frac{n}2\cdot\frac{n}1\\ &=\left(\frac{n}{n-1}\cdot\frac{n}{n-2}\cdot\dots\cdot\frac{n}2\right)n \end{align*}$$

If you know that $$\lim_{n\to\infty}\left(1+\frac1n\right)^n = e\;,$$ you can also look at the ratio of consecutive terms to see that the sequence grows almost exponentially:

$$\begin{align*} \frac{a_{n+1}}{a_n} &=\frac{\frac{(n+1)^{n+1}}{(n+1)!}}{\frac{n^n}{n!}}\\ &=\frac{(n+1)^{n+1}}{n^n}\cdot\frac{n!}{(n+1)!}\\ &=\frac{(n+1)^n(n+1)}{n^n}\cdot\frac1{n+1}\\ &=\frac{(n+1)^n}{n^n}\\ &=\left(\frac{n+1}n\right)^n\\ &=\left(1+\frac1n\right)^n \end{align*}$$

$\endgroup$
4
  • $\begingroup$ $n!<2^n$ so $\frac{n!}{n^n}<\frac{2^n}{n^n}=(\frac{2}{n})^n$ if $n>2$, $(\frac{2}{n})^n<\frac{2}{n}<\epsilon$ is this corrct $\endgroup$
    – ALMEra
    Nov 23, 2020 at 6:39
  • 1
    $\begingroup$ @noname: No, $n!>2^n$ for all $n\ge 4$. $\endgroup$ Nov 23, 2020 at 19:04
  • $\begingroup$ Thank you...... $\endgroup$
    – ALMEra
    Nov 23, 2020 at 19:56
  • 1
    $\begingroup$ @noname: You’re welcome. $\endgroup$ Nov 23, 2020 at 19:58
4
$\begingroup$

Can you show $n! \le n^{n-1}$? Then you'd have $n^n/n! \ge n^n/n^{n-1} = n$, and $\lim_{n \to \infty} n = \infty$, so $\lim_{n \to \infty} n^n/n! = \infty$ as well.

Of course this is a very crude bound, but $n^n$ is so much larger than $n!$ that you don't need to be careful.

$\endgroup$
1
  • $\begingroup$ Interesting approach, but the other hints were much easier to use. Sorry. $\endgroup$ Oct 31, 2011 at 23:44

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.