Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

"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.

share|improve this question
4  
Hint: $a_{n+1}/a_n=(1+1/n)^n$, whose limit when $n\to\infty$ should be clear. –  Did Oct 31 '11 at 23:29
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$. –  Davide Giraudo Oct 31 '11 at 23:29
2  
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$. –  Henning Makholm Oct 31 '11 at 23:30
    
If you are also convinced that for big $n$, one has $(n+1)!\leq n!$, you have done. –  Valerio Capraro Oct 31 '11 at 23:33
    
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. –  Alex Basson Oct 31 '11 at 23:55
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
Interesting approach, but the other hints were much easier to use. Sorry. –  Christian Ivicevic Oct 31 '11 at 23:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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