Which one is asymptotically larger: $n 2^n$ or $3^n$?

Question

Which of the following functions is larger asymptotically: $n 2^n$ or $3^n$?

If I take $\log$ on both functions and then compare, I am getting $n 2^n$ as larger, but the answer given is $3^n$. Where am I going wrong?

$n 2^n$ vs. $3^n$ is equivalent to comparing $\log(n 2^n)$ vs. $\log 3^n$, or $\log_2 n +n$ vs. $n \log_2 3$, now how do I proceed?

Answer 1

Consider $\displaystyle f(x)=\sum_{n=0}^{\infty} x^n=\frac{1}{1-x}$ for $|x|<1$. Then $\displaystyle xf'(x)=\sum_{n=0}^{\infty} nx^n$.

Taking $x=\dfrac{2}{3}$ we see that the series for $xf'(x)$ converges and so $$ \lim_{n\to\infty}\dfrac{n 2^n}{3^n}=0 $$

This means that $3^n$ is asymptotically larger than $n2^n$.

By considering higher derivatives, we see that $3^n$ is asymptotically larger than $n^k2^n$ and so is asymptotically larger than $p(n)2^n$ for every polynomial $p$.

Answer 2

Let's consider $\dfrac {3^n} {n 2^n}$:

$$\frac {3^n} {n 2^n} = {\rm e} ^{\log \frac {3^n} {n 2^n}} = {\rm e} ^{\log 3^n - \log (n 2^n)} .$$

Now

$$\log (3^n) - \log (n 2^n) = n \log 3 - \log n - n \log 2 = n \left( \log 3 - \log 2 - \frac {\log n} n \right)$$

and

$$\lim \limits _{n \to \infty} \frac {\log n} n = 0, \quad \log 3 - \log 2 > 0 ,$$

so

$$\lim \limits _{n\to \infty} \frac {3^n} {n 2^n} = \infty .$$