Prove $(n!)/n^n \leq 1/2^{k}$, where $k$ is the floor of $n/2$.

Question

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?

Answer 1

Rather than proceeding by induction, note that \begin{align*} \frac{n!}{n^n} \leq \frac{k!}{n^k} \frac{n(n-1) \cdots (k+1)}{n^{n-k}} \leq \frac{k!}{n^k} = \left(\frac{1}{n}\right) \cdots \left(\frac{k}{n}\right) \leq \frac{1}{2^k}, \end{align*} since $k\leq 2n$.

Answer 2

Use $(n+1)^n = n^n \left(1+\frac{1}{n}\right)^n$ and prove $\left(1+\frac{1}{n}\right)^n\geq 2$ using binomial theorem.

Answer 3

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

Answer 4

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<n^n.$$