0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! Neat trick. I'll be sure to remember that... $\endgroup$ – Zappa Nov 7 at 10:18
  • $\begingroup$ You are welcome :-) $\endgroup$ – trancelocation Nov 7 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.