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

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

One comment

  1. 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

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