Proof that $n!\leq {(\frac{n+1}{2})}^{n}$ [duplicate]

Solution 1:

Write, for $n\geq1$,

$$n!=1\times2\times\dots\times n\\=n\times (n-1)\times\dots\times 1$$

Then, multiply corresponding factors:

$$n!^2=(n\times1)\times((n-1)\times2)\times\dots\times(1\times n)$$

Inside the paretheses, you have $i\times(n+1-i)$ for $i\in\{1\dots n\}$.

Next, notice that $i\times (n+1-i)$, as a function of real $i$, is maximum for $\frac{n+1}2$ (it's a parabola, and the maximum is obtained in the midpoint between the roots). And this maximum is $\frac{n+1}{2}\left(n+1-\frac{n+1}{2}\right)=\left(\frac{n+1}{2}\right)^2$.

So each parenthesis in the preceding product is less than or equal to $\left(\frac{n+1}{2}\right)^2$, and

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

Finally

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

Solution 2:

The claim is a straightforward consequence of the AM-GM inequality, $$ n!=\prod_{k=1}^{n}k<\left(\frac{1}{n}\sum_{k=1}^{n}k\right)^n = \left(\frac{n+1}{2}\right)^n.$$ For an improved bound, we may consider that for any $n\geq 2$ $$ \log(n!)=\sum_{k=1}^{n}\log(k) = n\log(n)-\sum_{k=1}^{n-1}k \log\left(1+\frac{1}{k}\right) $$ follows from summation by parts, and since $\frac{\log(1+x)}{x}>\frac{1}{1+\frac{x}{2}}$ over the interval $(0,1)$, $$ \log(n!) < n(\log n-1)+\sum_{k=0}^{n-1}\frac{1}{2k+1}<n(\log n-1)+1+\frac{\log n}{2} $$ hence, by exponentiation, $$ n! < \color{red}{e\sqrt{n}\left(\frac{n}{e}\right)^n}.$$

By refining the last approach through creative telescoping, we may also prove Stirling's inequality: $$ \left(\frac{n}{e}\right)^n \sqrt{2\pi n} \exp\left(\frac{1}{12n+1}\right) < n! < \left(\frac{n}{e}\right)^n \sqrt{2\pi n} \exp\left(\frac{1}{12n}\right).$$

Solution 3:

Proof by induction.

$$1! \le \dfrac{(1+1)\ ^ 1}{2} = 1 $$ Assume for all n (that the inequality holds) , and prove for n+1: $$ (n+1)! = (n+1)*n! \le (n+1)*\dfrac{(n+1) \ ^ n}{2} = \dfrac{(n+1) \ ^ {n+1}}{2} \le \dfrac{(n+1 +1) \ ^ {n+1}}{2} = \dfrac{(n+2) \ ^ {n+1}}{2}$$

in the first inequality I used the I.H.