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.

  • 4
    Hint: $a_{n+1}/a_n=(1+1/n)^n$, whose limit when $n\to\infty$ should be clear.2011-10-31
  • 1
    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$.2011-10-31
  • 3
    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$.2011-10-31
  • 0
    If you are also convinced that for big $n$, one has $(n+1)!\leq n!$, you have done.2011-10-31
  • 0
    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.2011-10-31
  • 0
    See also [this question](http://math.stackexchange.com/questions/579825/compute-the-limit-lim-n-to-infty-fracnnn) and [other posts linked there](http://math.stackexchange.com/questions/linked/579825).2015-10-03

2 Answers 2

5

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

3

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.

  • 0
    Interesting approach, but the other hints were much easier to use. Sorry.2011-10-31