Prove $(n!)/n^n \leq 1/2^{k}$, where $k$ is the floor of $n/2$. I suppose the natural way to prove this is by induction. When I follow the rather natural steps $$\frac{(n+1)!}{(n+1)^{n+1}} = \frac{n!}{(n+1)^{n}} \leq \frac{n!}{(n)^{n}}$$ in order to apply the induction hypothesis, however, I obtain for $n+1$ exactly the same bound I assumed for $n$. This is not a problem if $n+1$ is odd, because then the floor of $n/2$ and $(n+1)/2$ coincide, but how can I "detect" the change in the case that $n + 1$ is even?
HINT:
$$\frac{n!}{n^n} = \left( \frac{1}{n} \cdot \frac{2}{n} \cdots \frac{n/2}{n} \right) \cdot  \cdots \frac{n-1}{n} \frac{n}{n}  \leq \left( \frac{1}{2} \cdots \frac{1}{2} \right) \cdot 1 \cdots 1 = \frac{1}{2^k}$$
This is obvious:
$$2^k\cdot n!=2(2\cdot 2)\cdots(2\cdot\lfloor \frac{n}{2}\rfloor) \cdot (\lfloor \frac{n}{2}\rfloor+1)\cdots n&lt;n^n.$$