How to prove $ \frac{n}{2}^\frac{n}{2} \leq n! $ using induction While proving that $n! \leq n^n $ using induction is easy, and showing that $ \frac{n}{2}^\frac{n}{2} \leq n! $ by comparing each term of the product does work, I've struggled to come up with a successful way of showing the latter through induction
$$ \frac{k+1}{2}^\frac{k+1}{2} \leq (k+1)! $$
$$ \sqrt{\frac{k+1}{2}} \cdot \frac{k+1}{2}^\frac{k}{2} \leq (k+1)k! $$
$$ \frac{k+1}{2}^\frac{k}{2} \leq \sqrt{2k+2} \cdot k! $$
This is what's seemed to me to be the most promising but I can't seem to take it any further, or find any productive way to apply the inductive assumption
Following @gimusi's hint, by dividing both sides by $ \sqrt{\frac{k+1}{2}}$, which then leads to the result of having to prove:
$$ (2k+2)^\frac{1}{k} \leq \frac{k+1}{k} $$
which would be easy to show if it was $ \frac{k}{k+1} $ since it would be smaller than 1, but as it is I can't find a straightfoward way to progress
 A: You may also proceed as follows:
First note that
$$\left( \frac{n}{2}\right)^{\frac{n}{2}} \leq n! \Leftrightarrow \left( \frac{n}{2}\right)^{n} \leq (n!)^2 \Leftrightarrow \boxed{n^n \leq 2^n (n!)^2} $$
Now, you may show the boxed inequality. To do so the following two facts are useful:


*

*$\color{blue}{(\star)}$: $\frac{1}{n^k} \binom nk = \frac{1}{k!}\frac{n \cdot \ldots \cdot (n-k+1)}{n^k} \leq 1$

*$\color{blue}{(\star\star)}$: $\Rightarrow \color{blue}{(n+1)^n} = \sum_{k=0}^n \binom nk n^{n-k} = \sum_{k=0}^n \frac{1}{n^k} \binom nk n^{n} \color{blue}{\stackrel{(\star)}{\leq}} \sum_{k=0}^n n^{n} = \color{blue}{ (n+1)n^n}$
Now, the induction step $n \rightarrow n+1$ looks as follows:


*

*Induction hypothesis: $\color{blue}{(IH)}$: $2^n (n!)^2 \geq n^n$

*Induction step:


$$2^{(n+1)}((n+1)!)^2 = 2^n\cdot (n!)^2 \cdot 2(n+1)^2 $$
$$\stackrel{\color{blue}{(IH)}}{\geq} n^n \cdot 2(n+1)^2 = 2(n+1)\cdot \color{blue}{(n+1)n^n}$$
$$\color{blue}{\stackrel{(\star\star)}{\geq}} 2(n+1)\cdot \color{blue}{(n+1)^n} \geq (n+1)^{n+1}$$
A: HINT
We have that


*

*base case: $n=1 \implies 1\ge \frac{\sqrt 2}2$

*induction step: assuming true $n! ≥ (n/2)^{n/2}$ we need to prove that $(n+1)! ≥ ((n+1)/2)^{(n+1)/2}$
therefore we have
$$(n+1)! =(n+1)n!\stackrel{Ind. Hyp.}\ge  (n+1)(n/2)^{n/2}\stackrel{?}\ge((n+1)/2)^{(n+1)/2}$$
then we need to prove that
$$(n+1)(n/2)^{n/2}\stackrel{?}\ge((n+1)/2)^{(n+1)/2}$$
squaring both sides and simplifying we obtain
$$(n+1)n^{n}\stackrel{?}\ge \frac12(n+1)^{n}$$
