Proving that $n! \leq 2*(\frac{n}2)^n$

Question

I am learning how to prove various statements and stumbled upon this one: $$n! \leq 2\cdot \Bigl(\frac{n}2\Bigr)^n$$

My question is, if I got a statement like this, how do I find the best possible way of proving it? I usually start with induction, since $n$ is an arbitrary natural number. I tried that, but then I will inevitably come across a term, which I cannot simplify any more. So if induction does not work, I usually move on and try to find obvious inequalities which are "known" or which I can immediately infer from ordering axioms. But this is where it gets tricky.

Any hints on how to solve this particular inequality and on how to approach problems of this sort generally? I appreciate any help, thanks!

Answer 1

Let us square both sides: $$(n!)^2 \leq 4 \cdot \left( \frac{n}{2}\right)^{2n}$$

Let's write down all factors of $(n!)^2$ in a grid and combine the factors: $$ \begin{array}{rlccccccccccccc} (n!)^2 &= &n &\cdot & (n-1) & \cdot &(n-2) &\cdot &\cdots & \cdot & 2 & \cdot & 1 & & \\ &&& \cdot & 1 & \cdot & 2 & \cdot & \cdots & \cdot & (n-2) &\cdot &(n-1) & \cdot & n\\ &= & n & \cdot &(n-1)\cdot 1 &\cdot &(n-2)\cdot 2 &\cdot &\cdots &\cdot &2\cdot(n-2) & \cdot &1\cdot(n-1) &\cdot &n \end{array} $$ Applying the AM-GM inequality to each of the factors, except the leading $n$ and the trailing $n$, we find: $$(n!)^2 = n^2 \cdot \prod_{i=1}^{n-1}\left((n-i)\cdot i\right)\leq n^2\prod_{i=1}^{n-1} \left(\frac{ (n-i)+i}{2}\right)^2 = n^2\left(\frac{n}{2}\right)^{2(n-1)} = 4 \cdot \left(\frac{n}{2}\right)^{2n}$$ Finally, take the square root of both sides and you obtain: $$n! \leq 2 \cdot\left(\frac{n}{2}\right)^{n}.$$

Answer 2

The inequality is true for $n=1$. For $n>1$, we have $$ n! \leq 2\cdot \Bigl(\frac{n}2\Bigr)^n\iff(n-1)!\leq\left(\frac{n}{2}\right)^{n-1}\iff\prod_{i=1}^{n-1}i\leq\left(\frac{1}{n-1}\sum_{i=1}^{n-1}i\right)^{n-1} $$ which is true thanks to AM-GM.

Some intuition for this solution: there are (i) the product of numbers $1,\dots,n$, (ii) something raised to power $n$, and (iii) a simple known formula for $1+\cdots+n$. All these suggest a use of AM-GM.

Answer 3

By induction.

For $n=0,1$, it is true.

Let $n\geq1$ such that

$$n!\leq 2.\left(\frac{n}{2}\right)^n$$

$($HR$)$.

Put $u_k=\left(1+\frac{1}{k}\right)^k\;\;$for $k\geq1$.

We have

$$\lim_{k\to+\infty}u_k=e$$

$u_1=2$, and

$(u_k)_{k\geq1} $ is increasing by ratio test.

Thus,

$$(\forall k\geq1)\;\; 2\leq\left(\frac{k+1}{k}\right)^k$$

$\implies$

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

$\implies$

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

$\implies $ by $($HR$)$.

$$(n+1)!\leq 2\cdot\left(\frac{n+1}{2}\right)^{n+1}.$$

Q.E.D.