# Stuck On A Proof By Induction

I need to prove true for all integers greater than and equal to 1 using induction.

I'll skip the base case, and the inductive assumption, and jump straight to the inductive step:

=

What I've done now is to say that is less than . But I don't know what to do from beyond there.

• Can you type the steps out in MathJax please? Sep 8, 2018 at 3:04
• @RushabhMehta Okay, I've done that.
– user590211
Sep 8, 2018 at 3:17
• First hint: When proving an inequality "LHS $\leq$ RHS" (Left Hand Side $\leq$ Right Hand Side), start by writing LHS on its own. Then apply transformations that end up with RHS. Each transformation can only be an "=" or "$\leq$". Sep 8, 2018 at 3:17
• If you don't have to use induction, then the inequality is simply AM-GM for the first $n$ positive integers.
– dxiv
Sep 8, 2018 at 3:23
• @I'm sorry but first, the problem says to use induction, and secondly, I don't know what AM-GM is.
– user590211
Sep 8, 2018 at 3:24

One way by induction (as opposed to recognizing the inequality as just AM-GM for $1,2,\ldots,n\,$):   write the inequality to prove as $\,\color{blue}{2^n n! \le (n+1)^n}\,$, and take this to be the inductive assumption. Then, to prove the inductive step for $\,n+1\,$:

$$2^{n+1} (n+1)! = 2(n+1) \cdot \color{blue}{2^n n!} \;\;\le\;\; 2(n+1)\cdot\color{blue}{(n+1)^n} = 2(n+1)^{n+1}$$

To complete the inductive step, it is sufficient to show that the RHS is:

$$2(n+1)^{n+1} \le (n+2)^{n+1} \;\;\iff\;\; \left(\frac{n+2}{n+1}\right)^{n+1} \ge 2 \;\;\iff\;\;\left(1 + \frac{1}{n+1}\right)^{n+1} \ge 2$$

But the latter holds true by Bernoulli's inequality, which concludes the proof.

[ EDIT ]   To note that this particular case (positive integer exponent and $\ge1$ base) does not require the full power of Bernoulli's inequality, and the result can be simply derived from the binomial expansion $\,\left(1 + \frac{1}{n+1}\right)^{n+1}= 1 + \binom{n+1}{1}\cdot \frac{1}{n+1}+\ldots \ge 1 + (n+1)\cdot \frac{1}{n+1} = 2\,$.

• In my opinion, Bernoulli's inequality is more elementary than the binomial theorem. Look at the complexity of the proofs. Sep 8, 2018 at 4:05
• @martycohen I completely agree, though in practice I found it to be a lot less taught than the binomial expansion, which why I added the last edit.
– dxiv
Sep 8, 2018 at 4:07