I've got a task where i need to proove the asymptotic big-Theta equation:
$$
\log n! = \Theta(n \, \log n)
$$
$ \ $
Since $f(\mathit{n}) \in \Theta(g(\mathit{n}))$ means that $g(n)\cdot k{_1} \leq f(n) \leq g(n)\cdot k{_2}$, one way i can proove the equation above is to find the coefficients $k{_1}$ and $k{_2}$, considering that $f(n) = \log n! $ and $g(n) = n \, \log n$.
Things are pretty simple with $k{_2}$, because $\log n! = \sum_{i=1}^{n}\log i \leq n \, \log n$, so $k{_2} = 1$.
Finding $k{_1}$ is not so obvious. I tried to present $\log i = \log n^{\log{_n} i} = \log{_n} i \cdot \log n$, so we have:
$$
\frac{\log n!}{n \, \log n} = \frac{\log n \cdot \sum_{i=1}^{n} \log{_n} i }{n \, \log n} = \frac{\sum_{i=1}^{n} \log{_n} i }{n}
$$
So now i have to find $k{_1}$ that fits $k{_1} \cdot \sum_{i=1}^{n} \log{_n} i \geq n$. I guess and i see that $k{_1} \geq 2$ will do, but i cannot prove it.
In the description of the task it is written that a specific trick may be helpful, namely estimating sum of n elements by throwing away half of it's elements. I'll be grateful for any ideas concerning this matter, even ones that attempt to solve the problem by different approach.
$$\sum_{i=1}^n \log i \geq \sum_{i=n/2}^n \log i \geq \left(n-\frac{n}{2}\right)\log\frac{n}{2} = \frac{1}{2} \left(n\log n - n\right) \geq \frac{1}{3}n\log n$$ the last step holding for $n$ sufficiently large.
Following the comments, another way to show the (stronger) following statement: $$ \ln n! = n\ln n - n +o(n) $$ (which in particular implies $\log n! = n\log n + o(n\log n)$). This is done by a comparison series/integral, a technique that works usually well (good rule of thumb) for series of the form $\sum_{k=1}^n f(k)$ where $f\colon\mathbb{R}\to\mathbb{R}$ is a monotone function (and, say, continuous, for the sake of integration). Below is a step-by-step derivation.
Here, set $f=\ln\colon\mathbb{R}_+^\ast\to\mathbb{R}$. As $f$ is increasing, one has that for any fixed $j\in\mathbb{N}^\ast$ $$ \forall x\in[j,j+1],\quad f(j) \leq f(x) \leq f(j+1) $$ which implies, integrating all three terms between on $[j,j+1]$, an interval of size $1$: $$ f(j) = \int_j^{j+1} f(j)dx \leq \int_j^{j+1} f(x)dx \leq \int_j^{j+1}f(j+1)dx = f(j+1) \tag{$\dagger$} $$ Now, since $(\dagger)$ is true for every $j\geq 1$, we can sum the inequalities for $j$ ranging from $1$ to $n$: $$ \sum_{j=1}^n f(j) \leq \sum_{j=1}^n \int_j^{j+1} f(x)dx \leq \sum_{j=1}^n f(j+1) $$ which can be rewritten as $$ \sum_{j=1}^n f(j) \leq \int_1^{n+1} f(x)dx \leq \sum_{j=2}^{n+1} f(j) = \sum_{j=1}^{n+1} f(j) \tag{$\ddagger$} $$ (the last equality coming from the fact that here $f(1)=0$). Rearranging the inequalities of $(\ddagger)$, we obtain $$ \int_1^{n} f(x)dx \leq \sum_{j=1}^n f(j) \leq \int_1^{n+1} f(x)dx \tag{$\star$} $$ But recall that a primitive of $\ln$ is known (and equal to $x\mapsto x\ln x - x$), and thus $$\int_1^x f = x\ln x - x + 1$$ so that \begin{align*} \int_1^{n} f(x)dx &= n\ln n -n +1 = n\ln n - n + o(n)\\ \int_1^{n+1} f(x)dx &= (n+1)\ln (n+1) -n = n\ln (n+1) + \ln(n+1) - n \\ &= n\ln n + \underbrace{n\ln\left(1+\frac{1}{n}\right) + \ln(n+1)}_{=o(n)} - n \end{align*} Plugging this back into $(\star)$, we finally get $$ n\ln n - n + o(n) \leq \sum_{j=1}^n f(j) \leq n\ln n - n +o(n) $$ as claimed. $\square$