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.

How does one show that $n^n \notin O((n+1)!)$ without using limits? I've recently been trying to prove such results without limits, and this is one case that is still bothering me.

share|improve this question
    
What do you mean by without using limits? –  cardinal Sep 18 '11 at 23:46
    
I wrote an answer then deleted it, since I think it is not what you need. Anyway, the idea is to find a bound from above for $(n+1)!$ by taking logarithms: $$\log(n+1)!\le \int_1^{n+1}\log(x+1)\, dx.$$ Evaluating the integral and then exponentiating you get the desired bound: $(n+1)!\le e(n+1) ( n+1 / e)^{n+1}$. Can this be of some help to you...? –  Giuseppe Negro Sep 18 '11 at 23:46
    
Can't you just take out a few terms of the factorial? e.g. (rough estimates) Write $n! \leq n^{n-3} \cdot 3^3 = 27 n^{n-3} = O(n^{n-2})$. –  TMM Sep 18 '11 at 23:58

1 Answer 1

up vote 3 down vote accepted

I'm not sure what you mean by "without using limits" since Big O Notation by definition involves a limit.

At any rate, note that for all $n \geq 1$

$$ \frac{n^n}{(n+1)!} = \frac{n}{2} \frac{n}{3} \cdots \frac{n}{n+1} > \frac{n}{4}, $$

hence, clearly $n^n \notin O((n+1)!)$.

(The very crude bound I use comes from considering just the first and last term in the product and the fact that $n/k \geq 1$ for each $k \in \{3,\ldots,n\}$.)

share|improve this answer
    
If $n=2$, then $n/3 = 2/3 \leq 1$. What am I missing? –  Li-thi Sep 19 '11 at 0:22
    
If $n = 2$, then $n^n / (n+1)! = 4 / 6 > n / 4 = 1/2$. What are you missing? (Perhaps I'm not understanding where your doubt is coming from.) :) –  cardinal Sep 19 '11 at 0:32

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.