Prove by induction that: $\quad n!<(\frac{(n+1)}{2})^n$ for $n>1$
Hint: use the binomial theorem
for $\ n=2 $: $\quad 2!<(\frac{2+1}{2})^2=2.25 \;$, which is true.
I tried:
$(k+1)!<(\frac{k+2}{2})^{k+1}\\
(k)!(k+1)<(\frac{k+2}{2})^k(\frac{k+2}{2})$
And i'm basically stuck, i don't have any idea on how to continue. What does the hint mean? How can i use the binomial theorem in here? Any help would be appreciated!
Best Answer
You may proceed as follows:
To show is $(n+1)! < \left(\frac{n+2}{2}\right)^{n+1}$ under the assumption that $n! < \left(\frac{n+1}{2}\right)^{n}$ - the induction hypothesis (IH) - is true.
Hence,
$$(n+1)! = (n+1)n! \stackrel{IH}{<}(n+1)\left(\frac{n+1}{2}\right)^{n}$$
So, it remains to show that $$(n+1)\left(\frac{n+1}{2}\right)^{n} \leq \left(\frac{n+2}{2}\right)^{n+1}$$ $$\Leftrightarrow 2 \left(\frac{n+1}{2}\right)^{n+1} \leq \left(\frac{n+2}{2}\right)^{n+1}$$ $$\Leftrightarrow 2 \leq \left(1+\frac{1}{n+1}\right)^{n+1}$$ which is true because of the binomial theorem since for $n>1$ you have $$\left(1+\frac{1}{n+1}\right)^{n+1} = \sum_{k=0}^{n+1}\binom{n+1}{k}\frac{1}{(n+1)^k}\geq 1 + \frac{n+1}{n+1} = 2$$ Done.