# $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction

I have to show $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction.

This is where I am stuck:

$$\left( \frac{n+2}{2} \right)^{n+1} \geq \dots \geq =2 \left( \frac{n+1}{2} \right)^{n+1} = \left( \frac{n+1}{2} \right)^n(n+1) \geq n!(n+1) = (n+1)!$$

I approached this from both sides and this is the closest I can get. I realize that $n+2$ on the left has to be bigger than $n+1$ on the right, but I do not know who to show that it overpowers the factor two I have from the right.

What could I do to fill the dots? Currently, I just have it without the dots, but I would be happier if I could back it up.

-
This is tangential to the question, but it's very useful to know that $(n/3)^n \leq n! \leq (n/2)^n$ for all sufficiently large $n$. This is an extremely rough version of Stirling's formula, and in many applications it is all one needs. The inequalities can be derived by taking $k=2,3$ in applying the ratio test to the series $\sum_n (n/k)^n/n!$ (recall that $e = \lim_n (1 + 1/n)^n$). The same argument shows that $n! \geq (n/k)^n$ eventually holds if $k > e$, and the reverse eventually holds if $0 < k < e$. Seeing how $n!$ compares to $(n/e)^n$ is of course Stirling's formula territory. –  leslie townes Oct 26 '11 at 22:13

Assuming $n! \le \left( \frac{n+1}{2} \right)^n$ is true, carry the induction step

$$(n+1) n!\leq (n+1) \left(\frac{n+1}{2}\right)^n =2 \left(\frac{n+1}{2}\right)^{n+1} \stackrel{?}{\leq} \left(\frac{n+2}{2}\right)^{n+1}$$ But the last inequality is just $$2 \le \left( \frac{n+2}{n+1} \right)^{n+1} = \left( 1 + \frac{1}{n+1} \right)^{n+1}$$ It follows because: $$\left( 1 + \frac{1}{n+1} \right)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} \frac{1}{(n+1)^k} \ge \sum_{k=0}^{1} \binom{n+1}{k} \frac{1}{(n+1)^k} = 1 + (n+1) \frac{1}{n+1} = 2$$

-
Very cool, thanks a lot for breaking it down so much! –  queueoverflow Oct 26 '11 at 19:12

Hint:

$$(n+1)! = (n+1) n! \leq (n+1) \left( \frac{n+1}{2} \right)^n = 2 \left( \frac{n+1}{2} \right)^{n+1}.$$

You can check that $2 \left( \frac{n+1}{2} \right)^{n+1} \leq \left( \frac{n+2}{2} \right)^{n+1}$, by proving that

$$2 \leq \left( \frac{n+2}{n+1} \right)^{n+1}.$$

-
Maybe I do not look right, but isn't that what I have above just in reverse? –  queueoverflow Oct 26 '11 at 19:00
I did just rewrite what you have to a certain extent. That's fair. But now it's clear exactly what you have to to fill in the gaps. –  JavaMan Oct 26 '11 at 19:01
I was just too fast, now it helps. Thanks! –  queueoverflow Oct 26 '11 at 19:12

Hint: $$\left(\frac{n+2}{2}\right)^{n+1}=\frac{n+2}{2}\left(\frac{n+2}{n+1}\right)^n\left(\frac{n+1}{2}\right)^n.$$

Estimate $\left(\frac{n+2}{n+1}\right)^n$.

-

$\frac{((n+2)/2)^{n+1}}{((n+1)/2)^{n+1}} = (1 + \frac{1}{n+1})^{n+1} \ge 2$ by the binomial theorem.

-