# Proving that $n^n \notin O((n+1)!)$

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.

-
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

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\}$.)

-
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