Use induction to prove that the inequality, $n! < \left(\frac{n}{2}\right)^n$ continues to hold after $n=6$.

Question

I am confused how you would continue with the inductive step. Thanks

Answer 1

Basis step, $P_6 : 6!<(\frac{6}{2})^6\rightarrow 720<3^6=729$. True

Inductive step, suppose $P_n$ is true, prove that $P_{n+1}$ is also true.

Note $P_n:n!<(\frac{n}{2})^n$ and $P_{n+1}:(n+1)!<(\frac{n+1}{2})^{n+1}$

Observe that, $$\begin{align}(\frac{n+1}{2})^{n+1}&=(\frac{n}{2}+\frac{1}{2})^{n+1} \\&>(\frac{n}{2})^{n+1}+(n+1)\cdot\frac{n^n}{2^{n+1}}+\frac{n(n+1)}{2}\cdot(\frac{n^{n-1}}{2^{n+1}})\tag{binomial}\\&=\frac{(5n+3)}{4}\cdot(\frac{n}{2})^n\\&=(n+\frac{n+3}{4})\cdot(\frac{n}{2})^n\\&>(n+1)\cdot(\frac{n}{2})^n,\forall n\ge6\end{align}$$

So, start with $P_n$,

$$\begin{align}n!(n+1)&<(\frac{n}{2})^n\cdot(n+1)\\&<(\frac{n+1}{2})^{n+1}\end{align}$$