Big $O$ -- $3^n$ vs $n\cdot2^n$

Question

I'm trying to compare $f(n) = 3^n$ and $g(n) = n\cdot2^n$ to determine whether $f \in O(g)$, $f \in \Omega(g)$, or $f \in \Theta(g)$.

My gut is telling me that $g(n) = n\cdot2^n$ grows faster, and so $f \in O(g)$, but I'm having a hard time coming up with a rigorous argument. I've tried using limits but keep getting things like $0 \cdot \infty$.

Can anyone lend a helping hand?

Answer 1

Hint: For intuition, try taking the limit of the ratio

$$\lim_{n\rightarrow\infty}\frac{n2^n}{3^n}=\lim_{n\rightarrow\infty}n\left(\frac{2}{3}\right)^{n}$$

Answer 2

Here is a proof without limits, just an induction. We prove that for all positive integers $n$, we have $g(n)\leq 3f(n)$: for $n=1$, we have $g(1)=2$ and $f(1)=3$, so it's fine.

Now, we have

$$\begin{align*} g(n+1) &= (n+1)2^{n+1} = \color{red}{n2^n}\cdot 2 + 2^n\cdot 2 \\ &\leq \color{red}{3\cdot3^n}\cdot2 + \color{blue}{2^n}\cdot2\\ &\leq 3^{n+1}\cdot2 + \color{blue}{\frac{3\cdot3^n}{n}}2 \\ &= 3^{n+1}\cdot(2+\frac{2}{n})\\ &\leq 3^{n+1}\cdot 3 = 3f(n+1).\end{align*}$$

Therefore, we have $g=O(f)$.