Prove $(n!) ^2 > n^n$ for all $n > 3$ by induction.
I know that we will have to use Binomial theorem somehow but I can't figure out how?
Please provide some hint.
-
$\begingroup$ You don’t need binomial theorem, Bernoulli inequality suffices. $\endgroup$– userCommented Sep 17, 2018 at 7:09
3 Answers
HINT
Proceed as usual by
- base case
- induction step: $$(n!)^2>n^n \implies ((n+1)!)^2>(n+1)^{n+1}$$
then consider
$$((n+1)!)^2=(n+1)^2(n!)^2\stackrel{Ind. Hyp.}>(n+1)^2n^n\stackrel{?}>(n+1)^{n+1}$$
therefore to conclude we need to prove the last inequality that is
$$(n+1)^2n^n\stackrel{?}>(n+1)^{n+1}$$
-
$\begingroup$ Can you please explain the last step i.e. from (n+1)^2 n^n to(n+1)^n+1? $\endgroup$ Commented Sep 17, 2018 at 7:54
-
$\begingroup$ It is the step we need to prove, indeed note that I’ve put “?” for the inequality. $\endgroup$– userCommented Sep 17, 2018 at 8:01
-
$\begingroup$ @SaswatKumarPati Note that is we prove that inequality we can conclude form the chain $$((n+1)!)^2=(n+1)^2(n!)^2\stackrel{Ind. Hyp.}>(n+1)^2n^n>(n+1)^{n+1}$$ that $$((n+1)!)^2>(n+1)^{n+1}$$ which is the induction step. $\endgroup$– userCommented Sep 17, 2018 at 8:21
Hint for the induction step:
$(n+1)^2n^n>(n+1)^{n+1} \iff (1+1/n)^n<n+1$.
On the left side, $$\frac{(n+1)!^2}{n!^2}=(n+1)^2$$ and on the right side
$$\frac{(n+1)^{n+1}}{n^n}=(n+1)\left(1+\frac1n\right)^n=(n+1)\left(1+\frac nn+\frac{n(n-1)}{n^22!}+\frac{n(n-1)(n-2)}{n^33!}+\cdots\right).$$
Then
$$\left(1+\frac1n\right)^n=1+\frac nn+\frac{n(n-1)}{n^22!}+\frac{n(n-1)(n-2)}{n^33!}+\cdots<1+1+\frac12+\frac1{3!}+\cdots<e.$$