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?
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$.