Prove that $n \ln(n) - n \le \ln(n!)$ without Stirling
Recall that the sequence $$ e_n = \left( 1+ \frac 1n \right)^n $$ is increasing and converges to $e$. Thus, $$ e^n \ge e_1 \cdot e_2 \cdot \ldots \cdot e_n = \frac{(n+1)^n}{n!}. $$ In particular we obtain the weaker inequality $e^n \ge \frac{n^n}{n!}$, which is equivalent to $n \ln n - n \le \ln (n!)$.
A by-product of this is that the sequence $$ \sqrt[n]{e_1 \cdot e_2 \cdot \ldots \cdot e_n} = \frac{n+1}{\sqrt[n]{n!}} $$ is increasing and tends to $e$ (by an application of Stolz-Cesaro theorem).
As an alternative note that
$$ n \ln n - n \le \ln(n!)\iff e^{n \ln n - n}\le e^{\ln(n!)}\iff \frac{n^n}{e^n}\le n!$$
which can be proved by induction as follow
base case
- $n=1 \implies \frac1e \le 1$
induction step
assume $\frac{n^n}{e^n}\le n!$
$\frac{(n+1)^{n+1}}{e^{n+1}}=\frac{n+1}{e}\frac{(n+1)^n}{n^n}\frac{n^n}{e^n}\le \frac{n+1}{e}\left(1+\frac1n\right)^n n!\le(n+1)n!=(n+1)!$
$$ n \log n - n +1 = \int_1^n \; \; \log x \; \; dx < \sum_{j = 2}^n \log j \; = \log n! $$
diagram for $n=4$
