Proving $2^n = o(3^n)$

Question

I'm trying to prove that $2^n = o(3^n)$ using the definition of little-o alone. I'm having trouble because I can't seem to find a way to describe $n$ as a function of $c$ where $c$ is positive. Here's an example:

\begin{align}2^n &< c 3^n \\ \frac{2^n}{c} &< 3^n\\ \log_3{\frac{2^n}{c}} &< n\\ n\log_3{2} - \log_3{c} &< n\\ - \log_3{c} &< n - n\log_3{2}\\ \frac{-\log_3{c}}{1-\log_3 2} &< n, \end{align} but LHS is negative. If I multiply $-1$ on both sides it wont help, as now $n$ is less than that term.

Am I doing something terribly wrong?

Answer 1

Case 1: $c\ge 1$.

As $2<3$, we have (e.g. inductively) $2^n < 3^n \le c 3^n$ for all $n\ge 1 =:n_0$.

Case 2: $0<c<1$.

Now we use your calculation to see that we can use

$$n\ge n_0 := \frac{-\log_3 c}{1-\log_3 2}. $$ Note that this quantity is positive. e.g. for $c= 1/3$, $\log_3 c = -1$ so $n_0 = \frac1{1-\log_32} > 0$, since $\log_32\approx 0.631$.

Answer 2

Hint: $$ \frac{2^n}{3^n} = \left(\frac{2}{3}\right)^n$$

Answer 3

You wrote

$$(*) \quad \frac{-\log_3{c}}{1-\log_3 2} < n$$

and this is O.K !

You have to distinguish three cases:

1. $c=1$. In this case $(*)$ means $n>0.$ This is correct, since $2^n<3^n$ for all natural $n$.

2. $c<1.$ In this case $\frac{-\log_3{c}}{1-\log_3 2}>0$ and we have that $2^n<3^n$ for all $n> \frac{-\log_3{c}}{1-\log_3 2}.$

3. $c>1.$ In this case $\frac{-\log_3{c}}{1-\log_3 2}<0$ and we have $2^n<3^n$ for all natural $n$.

Answer 4

Note that $f=o(g)\iff \lim_{n\to\infty}f(n)/g(n)=0$ easily, by the squeeze theorem, say.

But it's easy to see that $2^n/3^n\to0$.

For instance, it is a strictly decreasing sequence, bounded beneath by $0$. So it converges. Call the limit $L$. Then $2/3L=L\implies L=0$.