Prove that $\log(n!)=\Theta(n\log n)$ without appealing to Stirling’s formula

Question

Problem

Prove that $\log(n!)=\Theta(n\log n)$ without appealing to Stirling's formula.

Can somebody please verify my solution to this problem?

Solution

In this solution, I am going to use the following Lemma without proof:

Lemma. If $n$ is a positive integer, then $\left(1+\dfrac{1}{n}\right)^n<3$.

(For a proof, this inequality follows directly from the result proven in this other post.)

We want to show that $\log(n!)=\Theta(n\log n)$.

First, we will show that $\log(n!)=O(n\log n)$, and then we will show that $n\log n=O(\log(n!))$.

1. Proof of $\log(n!)=O(n\log n)$:

   For $n\geq 1$, $\log(n!)\leq\log(n^n)=n\log n$, as required.

2. Proof of $n\log n=O(\log(n!))$:

   To show this, it's sufficient to prove the following Claim:

   Claim: $n\log n \leq 2\log(n!)$ for $n \geq 2$.

   Proof: The Claim is equivalent to $\log n^n \leq \log((n!)^2)$, which is true if $n^n \leq (n!)^2$. We will prove this by induction.

   • Induction hypothesis: $P(n)::=n^n \leq (n!)^2$.

   • Base case ($n=2$): $P(2)$ is true, because $2^2=4\leq (2!)^2=4$.

   • Inductive step: Assume $P(n)$ is true for some $n\geq 2$. We want to show that $P(n+1)$ is true:

     $$(n+1)^{n+1} \leq [(n+1)!]^2$$

     By the induction hypothesis, we have:

     $$n^n \leq (n!)^2$$

     Multiplying both sides by $\dfrac{(n+1)^{n+1}}{n^n}$, we get:

     $$(n+1)^{n+1} \leq \dfrac{(n!)^2(n+1)^{n+1}}{n^n}$$

     To prove $P(n+1)$, we want to show that

     $$\dfrac{(n!)^2(n+1)^{n+1}}{n^n}\leq [(n+1)!]^2$$

     But $[(n+1)!]^2=(n+1)^2(n!)^2$, so the above inequality is equivalent to:

     $$\dfrac{(n+1)^{n+1}}{n^n}\leq (n+1)^2$$

     This inequality becomes:

     $$\left(1+\dfrac{1}{n}\right)^n\leq n+1$$

     By the Lemma stated in the beginning of this solution, the expression $(1+1/n)^n$ has an upper bound of $3$ for all positive integers $n$. And, since $n \geq 2$, we have $n+1 \geq 3$. So, the above inequality is true, because:

     $$\left(1+\dfrac{1}{n}\right)^n\leq 3\leq n+1$$

     This proves $P(n+1)$.

   We have proven the Claim, which implies that $n\log n=O(\log(n!))$.

EDIT

---

Based on the hint in Milten's answer, here is an attempt at a shorter proof for $n\log n=O(\log(n!))$:

$$\begin{aligned}
\log n!&= \sum_{m=1}^n \log m\ge \sum_{m=\lceil n/2\rceil}^n \log m\\
&\ge (n/2)\log(n/2)\\
&= (n/2)\log n – (n/2)\log 2\\
&\ge (n/2)\log n – (n/2)\log 2\cdot\frac{\log n}{2\log 2}&\text{ (for }n\ge 4\text{)}\\
&= (n/2)\log n – (n/4)\log n\\
&= \dfrac{1}{4}n\log n\\
\end{aligned}$$

So, $n\log n\leq 4\log n!$ for $n\geq 4$. This shows that $n\log n=O(\log n!)$.

Answer 1

Hint:

$$\sum\log i\sim\int\log t\, dt$$

You can add details to obtain a precise bracketing, but this is the "heart" of the answer.