1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Can you type the steps out in MathJax please? $\endgroup$ – Don Thousand Sep 8 '18 at 3:04
  • $\begingroup$ @RushabhMehta Okay, I've done that. $\endgroup$ – user590211 Sep 8 '18 at 3:17
  • $\begingroup$ 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$". $\endgroup$ – Patrick Hew Sep 8 '18 at 3:17
  • $\begingroup$ If you don't have to use induction, then the inequality is simply AM-GM for the first $n$ positive integers. $\endgroup$ – dxiv Sep 8 '18 at 3:23
  • $\begingroup$ @I'm sorry but first, the problem says to use induction, and secondly, I don't know what AM-GM is. $\endgroup$ – user590211 Sep 8 '18 at 3:24
3
$\begingroup$

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\,$.

$\endgroup$
  • 1
    $\begingroup$ In my opinion, Bernoulli's inequality is more elementary than the binomial theorem. Look at the complexity of the proofs. $\endgroup$ – marty cohen Sep 8 '18 at 4:05
  • $\begingroup$ @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. $\endgroup$ – dxiv Sep 8 '18 at 4:07

Your Answer

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