How to derive the following inequality for all positive integers $n \geq 2$? $$ \frac{n!}{n^n} \leq \left(\frac{1}{2}\right)^k,$$ where $k$ denotes the greatest integer less than or equal to $\dfrac n2$.
We can write $$ \frac{n!}{n^n} = \frac{1}{n} \frac{2}{n} \cdots \frac{n}{n}. $$ What next?
I would be grateful for a proof by induction as well as a direct proof.
On
For $n=2$, check directly.
Note that the function $f(x)=\frac{x+1}{2x}$ is decreasing for $x>0$. Then, $f(x)\leq f(3)=2/3$ for $x\geq 3$.
For $n \geq 3$, and for each $j$, $1\leq j\leq n$, $$\frac jn\frac{n-j+1}n=\frac{\frac {(n+1)^2}4-\left(j-\frac {n+1}2\right)^2}{n^2}\leq\frac{(n+1)^2}{4n^2}\leq \frac49<\frac12$$
If $n$ is even, then $$\frac{n!}{n^n}\leq\left(\frac12\right)^{n/2}=\left(\frac12\right)^k$$
If $n$ is odd, then $$\frac{n!}{n^n}\leq\frac{n+1}{2n}\left(\frac12\right)^k<\left(\frac12\right)^k$$
\begin{align} \frac{n!}{n^n} &= \frac{\overbrace{1}^{\le \frac{n/2}{n}}}{n} \frac{\overbrace{2}^{\le \frac{n/2}{n}}}{n} \cdots \frac{\overbrace{k}^{\le \frac{n/2}{n}}}{n} \underbrace{\frac{k+1}{n} \cdots \frac{n}{n}}_{\le 1}\le \left(\frac{n/2}{n}\right)^k=\left(\frac{1}{2}\right)^k \end{align}