Proving by induction that $n! < (\frac{n+1}{2})^n$

Question

As an analysis homework I have to prove by induction that

$n! < (\frac{n+1}{2})^n : (2 \le n \in\mathbb{N})$

For $n = 2$ this is trivial, but for $n+1$ no matter how I transform the equation I can't seem to get $(\frac{n+2}{2})^{n+1}$ on the right-hand side. I'm sure that this is an easy homework and I'm missing something blatantly obvious but the closest I got was $(n+1)! < \frac{(n+2)^{n+1}}{2^{n}}$.

Any help is greatly appreciated.

Answer 1

By hypothesis, we have

$$\begin{align} (n+1)!&=(n+1)n!\\\\ &<(n+1)\left(\frac{n+1}{2}\right)^n\\\\ &=2\left(\frac{n+1}{2}\right)^{n+1}\end{align}$$

From Bernoulli's Inequality, we find that

$$\begin{align} \left(\frac{n+2}{2}\right)^{n+1} &=\left(\frac{n+1}{2}\right)^{n+1}\left(1+\frac{1}{n+1}\right)^{n+1}\\\\ &\ge 2\left(\frac{n+1}{2}\right)^{n+1} \end{align}$$

And we are done!

Answer 2

$$ \frac{ \left( \frac{n+1}{2} \right)^n}{\left( \frac{n}{2} \right)^{n-1}} \; \; = \; \; \frac{1}{2} \; n \; \left(1 + \frac{1}{n} \right)^n $$

Answer 3

A full derivation. Stop here if you only are looking for a hint.

Assume $$ n! < \left(\frac{n+1}{2}\right)^n $$ holds for some $n\geq 2$. Then, $$ (n+1)! = (n+1)n! < (n+1)\left(\frac{n+1}{2}\right)^n $$ by the induction hypothesis. Now, it remains to conclude to show that $$ (n+1)\left(\frac{n+1}{2}\right)^n \leq \left(\frac{n+2}{2}\right)^{n+1} $$ that is, rearranging, that $$ \left(\frac{n+1}{n+2}\right)^{n+1} \leq \frac{1}{2}. $$ But the LHS is $$ \left(\frac{n+1}{n+2}\right)^{n+1} = \left(1-\frac{1}{n+2}\right)^{n+1} = e^{(n+1)\ln\left(1-\frac{1}{n+2}\right)} \leq e^{-\frac{n+1}{n+2}} \leq e^{-\frac{3}{4}} < \frac{1}{2} $$ using first that $\ln(1+x) \leq x$, and then the monotonicity of $\exp$ (and the fact that $n\geq 2$).

Answer 4

It's worth noting that some induction proofs are more cleanly presented if you use $n-1$ for the inductive hypothesis. That is, let's assume we have $(n-1)!\lt\left(n\over2\right)^{n-1}$. Then

$$n!=n(n-1)!\lt n\left(n\over2\right)^{n-1}=2\left(n\over2\right)^n$$

and hence it suffices to show that

$$2\le\left(n+1\over n\right)^n=\left(1+{1\over n}\right)^n$$

This is perhaps easiest to show with a separate induction argument to establish that $(1+x)^n\ge1+nx$ for any $x$. In this case, using $n$ for the induction hypothesis works cleanly: If $(1+x)^n\ge1+nx$, then

$$(1+x)^{n+1}=(1+x)(1+x)^n\ge(1+x)(1+nx)=1+(n+1)x+nx^2\ge1+(n+1)x$$

Once you have $(1+x)^n\ge1+nx$ for any $x$, you can let $x={1\over n}$ and get

$$\left(1+{1\over n}\right)^n\ge1+n\cdot{1\over n}=1+1=2$$

Answer 5

Without induction and completely elementary:

$n! = \prod_{k=1}^n k $ so

$\begin{array}\\ n!^2 &= (\prod_{k=1}^n k)^2\\ &= (\prod_{k=1}^n k)(\prod_{k=1}^n k)\\ &= (\prod_{k=1}^n k)(\prod_{k=1}^n (n+1-k))\\ &= \prod_{k=1}^n k(n+1-k)\\ &= \prod_{k=1}^n (k(n+1)-k^2)\\ &= \prod_{k=1}^n \left(\dfrac{(n+1)^2}{4}-\dfrac{(n+1)^2}{4}+k(n+1)-k^2\right)\\ &= \prod_{k=1}^n \left(\dfrac{(n+1)^2}{4}-\left(\dfrac{(n+1)^2}{4}-k(n+1)+k^2\right)\right)\\ &= \prod_{k=1}^n \left(\dfrac{(n+1)^2}{4}-\left(\dfrac{n+1}{2}-k\right)^2\right)\\ &> \prod_{k=1}^n \left(\dfrac{(n+1)^2}{4}\right)\\ &= \left(\dfrac{(n+1)^2}{4}\right)^n\\ &= \left(\dfrac{n+1}{2}\right)^{2n}\\ \text{so}\\ n! &> \left(\dfrac{n+1}{2}\right)^{n}\\ \end{array} $