Estimating sum of n elements by throwing away half of elements 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.
 A: $$\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$
