Stuck On A Proof By Induction

217 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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