If $n\ge2$, prove that $\frac {n!}{n^n} \le ({\frac 1 2})^k$, where $k$ is the greatest integer $\le \frac n 2$.

Question

Using only precalculus knowledge, if $n\ge2$, prove that $\frac {n!}{n^n} \le ({\frac 1 2})^k$, where $k$ is the greatest integer $\le \frac n 2$. (taken from Apostol's Calculus I, page 46)

I don't have much of a clue, I tried substituting $k$ with the maximum value it can assume ($\frac n 2$) $$\frac {n!}{n^n} \le \left({\frac 1 2}\right)^{\frac n 2}$$ then squaring the expression $${{(n!)}^2 \over {n}^{2n}} \le \frac 1 {2^n}$$ and obtaining $$2^n(n!)^2\le n^{2n}$$ I mean, I can intuitively see that $$2n^2\cdot2(n-1)^2\cdots2\cdot2^2\cdot2\cdot1^2$$ (n times) is less than $$n^2\cdot n^2 \cdots n^2$$ (n times), but I'd like to have a more logically sound explanation, given that I didn't delve into calculus yet. Thanks in advance!

Answer 1

$\displaystyle\frac{n!}{n^n}=\frac{n(n-1)(n-2)\cdots2\cdot1}{n\cdot n\cdots n\cdot n}=\frac{n}{n}\frac{n-1}{n}\cdots\frac{k+1}{n}\frac{k}{n}\frac{k-1}{n}\cdots\frac{2}{n}\frac{1}{n}$

$\hspace{.4 in}\displaystyle\le \frac{k}{n}\frac{k-1}{n}\cdots\frac{2}{n}\frac{1}{n}\le\left(\frac{1}{2}\right)^k$

since $\displaystyle l\le k\implies l\le \frac{n}{2}\implies \frac{l}{n}\le\frac{1}{2}$.

Answer 2

Lets use mathematical induction.

• For $n=2$, we see that $\frac{2!}{2^{2}}=\frac{1}{2}=\big(\frac{1}{2}\big)^{1}$. For $n=3$, we see that $\frac{3!}{3^{3}}=\frac{6}{27}=\frac{2}{9}\leq\frac{1}{2}=\big(\frac{1}{2}\big)^{1}$.
• Assume now that for $n=2k$, we have $\frac{(2k)!}{(2k)^{2k}}\leq\big(\frac{1}{2}\big)^{k}$ and for $n=2k+1$, we have $\frac{(2k+1)!}{(2k+1)^{2k+1}}\leq\big(\frac{1}{2}\big)^{k}$.
• Then, we have $\frac{(2k+2)!}{(2k+2)^{2k+2}}=\underbrace{\frac{2k+1}{2k+2}}_{\leq\frac{1}{2}}\Big(\underbrace{\frac{2k}{2k+2}}_{<1}\Big)^{2k}\underbrace{\frac{(2k)!}{(2k)^{2k}}}_{\big(\frac{1}{2}\big)^{k}}\leq\big(\frac{1}{2}\big)^{k+1}$, i.e., the claim holds for $n=2k+2$. Further, we have $\frac{(2k+3)!}{(2k+3)^{2k+3}}=\Big(\underbrace{\frac{2k+2}{2k+3}}_{<1}\Big)^{2k+2}\frac{(2k+2)!}{(2k+2)^{2k+2}}\leq\frac{(2k+2)!}{(2k+2)^{2k+2}}\leq\big(\frac{1}{2}\big)^{k+1}$, i.e., the claim also holds for $n=2k+3$. This completes the last step of induction. Hence, the claim is true for all integers not less than $2$.