2
$\begingroup$

I need to find out through induction for which $n \geq 0$ the following inequality holds

$$3n+2^{n} \leq 3^n$$

clearly it does not work for n=1 and n=2, so my induction hypothesis is that it works for $n \geq 3$, however when performing the induction step, I am kind of stuck

because

$ n \rightarrow n+1$

$3 (n+1) + 2^{n+1} \leq 3^{n+1}$

$3(n+1) + 2^{n} \cdot 2 \leq 3^n \cdot 3$

I recreated the starting inequality within (overline)

$3n + 3 + 2^n + 2^n \leq (2+1) \cdot 3^n$

$2^n + 3 + \overline{3n + 2^n \leq 3^n} + 2\cdot 3^n$

I tried to show that what was added on the LHS is always smaller than on the RHS, therefor

$2n+3 \leq 2\cdot 3^n$

$2n + 3 \leq 3^n + 3^n$

so it is clear that this holds,but would the proof work that way? if yes, are there other, more elegant approaches?

$\endgroup$
5
$\begingroup$

Another way.

For $n\geq3$ by AM-GM we obtain: $$3^n-2^n=(3-2)\left(3^{n-1}+3^{n-2}\cdot2+...+3\cdot2^{n-2}+2^{n-1}\right)\geq$$ $$\geq n\sqrt[n]{3^{n-1+n-2+...+1}2^{1+...+n-1+n-2}}=n\cdot6^{\frac{n-1}{2}}\geq n\cdot6^{\frac{3-1}{2}}=6n>3n.$$

$\endgroup$
1
  • $\begingroup$ thank you very much for showing this approach $\endgroup$
    – Parinn
    Oct 21 at 23:45
3
$\begingroup$

So I think the necessary steps in the proof are all there, it is just better to do it slightly differently. You initially write $3(n+1) + 2^{n+1} \leq 3^{n+1}$ and then manipulate it. I know that's what you are trying to show, but you never want to manipulate what you are trying to show. Its nice form to start with one side of the inequality, and make your way to the other side. You don't want to write both sides at the same time. I would write the induction step as follows:

We want to show $3(n+1) + 2^{n+1} \leq 3^{n+1}$. By the induction hypothesis we know $3^n \geq 3n + 2^n$ so we can say \begin{align*} 3^{n+1} &= 3\cdot 3^n\\ &\geq 3(3n + 2^n)\\ &= 3(3n) + 2^n\cdot 3 \end{align*} Now since $n \geq 3$, we know $3n > n+1$ and of course $3 > 2$. So we make these substitutions and arrive at \begin{align*} &\geq 3(n+1) + 2^n\cdot 2\\ &= 3(n+1) + 2^{n+1}. \end{align*} Thus, we have shown the statement holds for $n+1$.

$\endgroup$

Your Answer

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

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