Trying to prove $\log\left(n!\right)$ is greater than or equal to $\left(\frac{n}{2}\log\left(n\right)\right)$

Question

I'm trying to prove that $\log\left(n!\right)$ is greater than $\left(\frac{n}{2}\log\left(n\right)\right)$ and I'm kinda stuck.

I could only prove $\log\left(n!\right)\ge\ \left(\frac{n}{2}\log\left(\frac{n}{2}\right)\right)$ and following is my prove:

\begin{align} \log(n!) &=\log(n\cdot(n-1)\cdot(n-2)\cdots(1))\\ &=\log(n)+\log(n-1)+\log(n-1)+\cdots+\log(1) \\ &\geq \log(n)+\cdots+\log(\frac{n}{2}) \\ &\geq \log(\frac{n}{2})+\log(\frac{n}{2})+\log(\frac{n}{2})+\cdots+\log(\frac{n}{2})\\ &= \frac{n}{2}\log(\frac{n}{2}) \end{align} But this is not helping me either because $\frac{n}{2}\log(n) > \frac{n}{2}\log(\frac{n}{2})$

and $\frac{n}{2}\log(\frac{n}{2}) = \frac{n}{2}\log(n) - \frac{n}{2}\log(2)$

What am I missing?

Answer 1

You're almost there -- just don't discard the second half of the sum (and deal with the "good" term $\log n$ separately):$$\begin{align} \log(n!) &= \sum_{k=1}^n \log k = \log n + \sum_{k=\frac{n}{2}+1}^{n-1} \log k + \sum_{k=2}^{\frac{n}{2}}\log k \\ &\geq \log n + \left(\frac{n}{2}-1\right)\log \frac{n}{2} + \left(\frac{n}{2}-1\right) \log 2 \\ &= \log n + \left(\frac{n}{2}-1\right)\log n - \left(\frac{n}{2}-1\right)\log 2 + \left(\frac{n}{2}-1\right) \log 2 \\ &= \frac{n}{2}\log n \end{align}$$

Answer 2

I provide you an estimate which is also asymptotically better.

You have $$ \log(n!) = \sum_{k=2}^n \log(k) \geq \sum_{k=2}^n \int_{k-1}^k \log(t)\,dt =\int_1^n \log(t)\,dt = 1-n+n\log(n), $$ which dominates $\frac12\log(n)$ for large $n$.

As a matter of fact, $n\geq 8\geq e^2$ is sufficient, because then $$ 1-n+n\log(n) \geq -n+n\log(n) \geq -n\frac12\log(n)+n\log(n) = \frac n2\log(n). $$

So you just need to check your inequality for $n=1,\dotsc,7$. Spoiler alert: it is true.

Answer 3

In fact, \begin{eqnarray*} \log(n!) &=&\frac12\big\{\log\big[n\cdot1]+\log\big[(n-1)\cdot2\big]+\cdots+\log\big[1\cdot n\big]\big\}\\ &\geq&\frac12\big\{\log(n)+\log(n-1)+\log(n)+\cdots+\log(n)\big\} \\ &=& \frac12n\log(n). \end{eqnarray*} Here $$ k(n-k+1)\ge n $$ is used.

Answer 4

Rewrite $2\log(n!)$: \begin{align} \log(n!)+\log(n!)&= \log 1+\log 2+\dots+\log(n-1)+\log n\\ &+\log n +\log(n-1)+\dots+\log 2+ \log 1 \\ &=\sum_{k=1}^n \log\bigl(k(n-k+1)\bigr) \end{align} Observe that, in the latter sum, for all $1\le k\le n$, we have $\;k(n-k+1)\ge n$, so $$2\log(n!)\ge\sum_{k=1}^n \log n=n\log n. $$

Answer 5

$\log x$ is a concave and slowly-increasing function on $\mathbb{R}^+$, hence $\log(n!)=\sum_{k=1}^{n}\log(k)$ can be easily managed by summation by parts. Actually $$ \log(n!)= n \log(n) -\sum_{k=1}^{n-1}k\log\left(1+\tfrac{1}{k}\right) $$ and for any $x\in[0,1]$ we have $\frac{x}{1+\frac{x}{2}}\leq \log(1+x)\leq\frac{x+\frac{x^2}{6}}{1+\frac{2x}{3}} $, hence $\log(n!)=\left(n+\frac{1}{2}\right)\log(n)+O(n)$.