# How to prove this is true?

The question is:

Show that $$\log_2(n!)\in O(n \log_2(n)).$$

I'm guessing I'll have to use principle of simple induction for this one. But how would I go about writing the proof for this? Should I use proof by cases?

What will be my first assumption? Usually the other proofs I wrote, there was a domain assumption and I assume x in set of integers, etc. Not sure what to write for this one.

Thanks for your help!

$$0 \le \log n! = \log \prod\limits_{k=1}^n k = \sum\limits_{k=1}^n \log k\le \sum\limits_{k=1}^n \log n = n\log n$$
Since $n!$ is the product of $n$ factors, each of which is at most $n$, it follows that $\log_2(n!)$ is the sum of $n$ summands, each of which is at most $\log_2n$.
Using the fact that $\log ab= \log a +\log b$, it should be straightforward to show by induction that $\log n! < n \log n$ for $n> 1$.
Stirling's approximation says that $$n! \sim \left( {n\over e}\right)^n {1\over \sqrt{2\pi n}}.$$ What happens when you take $\log_2$ of this?
First you should prove that $n!=O((n \ln n)^2).$ It implies $\ln n!=O(n \ln n)$.