Prove Statement with Asymptotic Notation

Question

The questions is to prove or disprove $n!=O(n^n)$ Using the definitions of big O, I consider: $n!<=n^n$ Using induction I get:
$P(1): 1<=1$
$P(k+1): (k+1)!<=(k+1)^{k+1}$

Then moving things around I end up with the left side as: $k(k+1)^{k+1}$ But I'm not sure that's correct. Is this correct and if not what do I do with the final step?

Answer 1

You don't have to do induction (or, at least, not as explicitly). Instead, you could note that $n!$ and $n^n$ are both the product of $n$ positive numbers, and in one of the products, all the factors are larger than in the other one.

Alternatively, $n!$ and $n^n$ both count the number of words of length $n$ you can make using an alphabet consisting of $n$ symbols, but one of them has the additional restriction that you must use each symbol exactly once.

If you want to do it the induction way, consider the following: $$ (k+1)^{k+1} = (k+1)(k+1)^k\geq (k+1)k^k \geq (k+1)\cdot k! = (k+1)! $$

All of these three approaches prove that $n!\leq n^n$ for all $n\geq 1$.

Answer 2

Why not just say $1\le n$, $2\le n$, ..., $n\le n$, and then multiply left- and right-hand sides to get $n!\le n^n = Mn^n$ for $M=1$ and all $n\in\mathbb N$, thus proving $n!=O(n^n)$.