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

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?

• Can you give your definition of $o(3^n)$? Also note that for $c<1$, $-\log_3 c$ is actually positive Sep 16 '19 at 5:01
• The LHS need not be negative : what if $c = 1$, for example? Also, from your calculation it is clear what function $n$ can be of $c$ : it can be $\left\lceil\frac{-\log_3 c}{1 - \log_3 2}\right\rceil + 1$, for example. Sep 16 '19 at 5:03
• @CalvinKhor The definition I'm using is: $f(n) = o(g(n))$ means for all $c > 0$ there exists some $n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n ≥ n_0$. Sep 16 '19 at 5:14

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.

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

• God, I feel so dumb not noticing I could split it into two cases. Thank you! Sep 16 '19 at 5:27
• @bnoite its not required, but I think this is easier to understand. There's actually nothing wrong with getting $n>$ negative, it just means you can take every $n\ge0$ (I chose $n_0 = 1$ to fit your definition) Sep 16 '19 at 5:30

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

• I've tried that: I always end up with $n < \frac{\log_2{c}}{\log_2{\frac{2}{3}}}$. I need $n$ to be greater then the other term. Sep 16 '19 at 5:20
• $\log_2\frac23\lt0$. So your inequality flips.
– user403337
Sep 16 '19 at 6:16

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

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