Is $n^K*2^n$ in $O(3^n)$?

Question

I need to prove or disprove that $n^K⋅2^n$ is in $O(3^n)$, $K$ being a constant $>0$. I suspect logarithms will be involved, moreover I suspect that $n^K⋅2^n$ is indeed in $O(3^n)$, but do not know how to reason from there. Please help!

Edit: I use the following definition for the big O: $f(n) ∈ O(g(n)) \equiv \{\exists k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot g(n)\}$

Answer 1

I assume $K>0^, otherwise it is trivial.

If $f(n)\in O(3^n)$ then there exists a constant $\varepsilon>0$ and a natural $M$ such that for all $n>M$, $f(n)<\varepsilon\cdot 3^n$.

Hence in your case:

$n^K\cdot 2^n=e^{n\cdot\ln 2+K\ln n}<e^{n\ln 3+\ln c}$

which holds true if

$n\cdot\ln 2+K\ln n<n\ln 3+\ln c$

rearranging...

$K\ln n<n(\ln 3-\ln 2)+\ln c$

and hence

$\ln n<n\frac{\ln\frac{3}{2}}{K}+\frac1{K}\cdot\ln c$

which holds always true for big enough $n$.