-4
$\begingroup$

I need to prove the following using mathematical induction:

$$2^n+1\leq 3^n\qquad\forall n\in\Bbb{Z^+}$$

Been working on this problem for a while and cannot figure it out. Any guidance or help would be appreciated on how to start or complete the inductive step, the part that is tripping me up.

$\endgroup$

closed as off-topic by user223391, user228113, user147263, zarathustra, JonMark Perry Dec 27 '15 at 8:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, Community, Community, zarathustra, JonMark Perry
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ using induction i got 4^k+1<=9^k $\endgroup$ – barbarian Apr 16 '15 at 20:04
  • 1
    $\begingroup$ @avid19 The hope is that your comment would be true, but more often than not it is not really true. Usually if there is a question like this...I prefer to either give a partial answer (as I have done here), downvote, downvote and vote to close, flag, etc. Think to yourself like the Count of Monte Cristo: "Do you worst, for I will do mine!" $\endgroup$ – Daniel W. Farlow Apr 16 '15 at 20:32
1
$\begingroup$

For $n=1$, $2^1+1=3=3^1$. It is proved for $n=1$

Assume it is true for $n$.

$2^{n+1}+1=2(2^{n}+1)-1\leq 2\cdot3^n-1\leq 2\cdot 3^n<3^{n+1}$

$\endgroup$
1
$\begingroup$

Here is the meat of the induction step: \begin{align} 3^{k+1} &= 3^k\cdot 3\tag{by definition}\\[0.5em] &\geq (2^k+1)\cdot 3\tag{by ind. hyp.}\\[0.5em] &=3\cdot 2^k+3\tag{expand}\\[0.5em] &> 2\cdot 2^k+1\\[0.5em] &= 2^{k+1}+1. \end{align}

$\endgroup$
1
$\begingroup$

The inequality is trivial for $n=1$. Suppose it holds for $n=p$. Then $$2^{p+1}+1 = 2\cdot 2^p+1 =2^p+2^p+1$$ which by assumption $$\leq 2^p+3^p \leq 3^p+3^p=2\cdot 3^p\leq 3\cdot 3^p=3^{p+1}$$ so the inequality holds for $n=p+1$. The induction axiom then tells that the inequality is true for any natural number.

$\endgroup$
  • $\begingroup$ Please see this tutorial for how to properly typeset your questions and answers. $\endgroup$ – Daniel W. Farlow Apr 16 '15 at 20:26
  • $\begingroup$ I have taken the liberty of trying to clean up your answer so you can see how to do it yourself. Please correct my edit if I messed something up by accident. $\endgroup$ – Daniel W. Farlow Apr 16 '15 at 20:36

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