How to prove $ \frac{n}{2}^\frac{n}{2} \leq n! $ using induction

Question

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

Answer 1

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}$$

Answer 2

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}$$