# Prove that $n!\leq(\frac{n}{2})^n$ for all $n\geq 6$

This is what I have so far. How do I continue the induction step?

For n=6, this is true since $$720\leq 729$$ Suppose $$n!\leq(\frac{n}{2})^n$$ holds for all $$n\geq 6$$ Want to prove that it holds for n+1, That is $$(n+1)!\leq(\frac{n+1}{2})^{n+1}$$ for all $$n\geq 6$$

First, we check the base case. That is, as you showed, the statement is true for $$n=6$$. Indeed: $$6! \leq (\frac{6}{2}^6)$$ $$\implies 720 \leq 3^6 = 729$$ Now we assume that the given statement is true for an arbitrary element $$k$$ in the set of Natural Numbers $$\mathbb N$$. So we suppose

$$k! \leq (\frac{k}{2})^k \ \ k \geq 6$$

is a true statement. Now, if we show this statement also holds for $$n = k+1$$ then we are done. That is, we want to show

$$(k+1)! \leq (\frac{k+1}{2})^{k+1}$$

Now remember, for example, we can write $$5!$$ as $$5 \cdot 4!$$. Therefore, we can write

$$(k+1)! = k!\cdot (k+1)$$

Now what do we know about $$k!$$? Well we assumed $$k! \leq (\frac{k}{2})^k$$. So we can write

$$(k+1)! = k! \cdot (k+1) \leq (\frac{k}{2})^k \cdot (k+1)$$

The last thing we need to do is to show $$(\frac{k}{2})^k \leq \frac{(k+1)^k}{2^{k+1}}$$. I will leave this to you, but you could convince yourself it is the case. Keep in mind $$k \geq 6$$.

Putting the pieces together, it follows $$(k+1)! \leq (\frac{k+1}{2})^{k+1}$$

This shows the statement is true by mathematical induction.

Hint: So as $$n! \leq(\frac{n}{2})^n$$ (from the induction assumption), we have $$(n+1)! = n! (n+1)\leq(\frac{n}{2})^n (n+1) = \frac{n^n(n+1)}{2^n}$$. Now it is enough to prove that $$\frac{n^n}{2^n} \leq \frac{(n+1)^n}{2^{n+1}} \Leftrightarrow n^n \leq \frac{(n+1)^n}{2}$$. Get $$\log$$ from two side: $$n\log(n) \leq n \log(n+1) - \log(2) \Leftrightarrow log(2) \leq n (\log(n+1)-\log(n)) = n\log(\frac{n+1}{n}) \\ \Leftrightarrow 2 \leq (1 + \frac{1}{n})^n$$.

As $$(1+\frac{1}{n})^n$$ increases monotonoically (you can see for $$x > 0$$ the derivative function of $$(1+\frac{1}{x})^x$$ is greater than zero) and for $$n = 6$$ we have $$(1+\frac{1}{6})^6 > 2.5$$ you can prove the inequality.