Prove an inequality on the ratio of n! to the nth power of n

Prove

$\frac{n!}{n^n} \leq \left( \frac{1}{2} \right)^k$

where $n \geq 2$ and $k$ is the greatest integer less than or equal to $n/2$ .

Proof. The proof is by induction. For the case $n=2$ we have on the left,

$\frac{n!}{n^n} = \frac{2!}{2^2} = \frac{1}{2}.$

On the right, we have

$\left( \frac{1}{2} \right)^k = \frac{1}{2}$

since $n/2 = 2/2 = 1$ implies $k = 1$ (since 1 is the greatest integer less than or equal to $n/2$ ).
Assume then that the inequality is true for some $n = m \in \mathbb{Z}_{\geq 2}$ . Then,

$\begin{align*} &&\frac{m!}{m^m} &\leq \left( \frac{1}{2} \right)^k \\ \implies && \left( \frac{m!}{m^m} \right) \left( \frac{(m+1)m^m}{(m+1)^{m+1}} \right) &\leq \left( \frac{1}{2} \right)^k \left( \frac{(m+1) m^m}{(m+1)^{m+1}} \right) \\ \implies && \frac{(m+1)!}{(m+1)^{m+1}} &\leq \left( \frac{1}{2} \right)^k \cdot \left( \frac{m}{m+1} \right)^m. \end{align*}$

But, from part (b) of this exercise we have

$m^p < \frac{(m+1)^{p+1} - m^{p+1}}{p+1}$

for all $p \in \mathbb{Z}_{>0}$ (and, in particular, must hold for $m-1$ , which will use in the following). So,

$\begin{align*} &&(p+1)m^p &< (m+1)^{p+1} - m^{p+1} \\ \implies&& m^{p+1} + (p+1)m^p &< (m+1)^{p+1} \\ \implies && m^m + m^m &< (m+1)^m & (\text{let } p = m-1)\\ \implies && 2m^m &< (m+1)^m \\ \implies && \left(\frac{m}{m+1} \right)^m &< \frac{1}{2}. \end{align*}$

Thus, we plug this back in to the inequality above and have,

$\frac{(m+1)!}{(m+1)^{m+1}} \leq \left( \frac{1}{2}\right)^k \cdot \left( \frac{m}{m+1} \right)^m \leq \left(\frac{1}{2}\right)^{k+1}.$

Notice that the inequality we have arrived at as $(1/2)^{k+1}$ as opposed to the $(1/2)^k$ we want. This is to deal with the fact that $k$ is the greatest integer in $m/2$ . This takes care of that problem since to complete the proof by induction we need to show that if the inequality holds for $m$ , then it holds for $m+1$ . If $m$ is even, then $k = m/2$ and $k+1 = (m+1)/2$ . On the other hand, if $m$ is odd, then $k = (m+1)/2$ . In either case though we have, $k+1 \leq (m+1)/2$ , so

$\frac{(m+1)!}{(m+1)^{m+1}} \leq \left( \frac{1}{2} \right)^{k+1} \leq \left( \frac{1}{2} \right)^{\lfloor \frac{m+1}{2}\rfloor}.$

Hence, the inequality holds for the case $m+1$ if it is true for any $m \in \mathbb{Z}$ .
Thus, the inequality is true for all $n \in \mathbb{Z}_{\geq 2}. \qquad \blacksquare$

8 comments

August 28, 2019 at 9:19 pm

richardsull says:

Here’s a proof that I think is a little cleaner:

For the inductive step, notice that

$\frac{(n+1)!}{(n+1)^{n+1}} = \frac{n!}{(n+1)^n} < \frac{n!}{n^n} \le (1/2)^k$

where k is the greatest integer less than or equal to n/2 (which I'll write as [n/2]).

When n is even, k = [n/2] = [(n+1)/2], and the inductive step is proven.

When n is odd, [(n+1)/2] = [n/2] + 1 = k + 1, so we can write

$(1/2)^k < (1/2)\cdot(1/2)^k = (1/2)^{k+1}$

and the inductive step is proven for odd n as well.

- July 9, 2020 at 3:42 pm
  
  richardsull says:
  
  Never mind. Disregard! Major mistake in the last step of my “proof”.
  
April 26, 2019 at 10:35 am

Artem says:

The part of inequality when m is even is probably wrong. First of all in this case

$k + 1 = (m+2)/2$

, not

$(m + 1)/2$

. However,

$m + 1$

is odd, so you have to prove that the left part is actually smaller than

$m/2$

, not

$(m+1)/2$

anyways. You first proof makes it possible for the $m/2 \leq \frac{(m+1)!}{(m+1)^{m+1}} \leq (m+2)/2$ .

- April 26, 2019 at 10:39 am
  
  Artem says:
  
  I of course meant powers:
  
  $(m+2)/2 \Rightarrow \frac{1}{2}^{\frac{m+2}{2}}$
  
  - July 7, 2019 at 9:47 pm
    
    Long Vo says:
    
    I think you’re right.
April 10, 2019 at 11:37 am

Scott says:

Maybe you can try to prove (n+1)^n >= 2n^n or (1+ 1/n)^n >= 2. (Use Bernoulli’s Inequality here).

- April 10, 2019 at 11:39 am
  
  Scott says:
  
  Then in the inductive step:
  (n+1)!/(n+1)^(n+1) = n!/(n+1)^n <= n!/(2n^n) .
  
September 11, 2017 at 11:37 am

Ed says:

Notice that the inequality we have arrived at as (1/2)^{k+1} as opposed to the (1/2)^k we want. This is to deal with the fact that k is the greatest integer in m/2. This takes care of that problem since to complete the proof by induction we need to show that if the inequality holds for m, then it holds for m+1. If m is even, then k = m/2 and k+1 = (m+1)/2+1/2. On the other hand, if m is odd, then k = (m-1)/2 and k+1= (m+1)/2 In either case though we have, k+1 \geq (m+1)/2

Stumbling Robot

Prove an inequality on the ratio of n! to the nth power of n

Related

8 comments

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment): Cancel reply