0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Can you give your definition of $o(3^n)$? Also note that for $c<1$, $-\log_3 c$ is actually positive $\endgroup$ Sep 16 '19 at 5:01
  • $\begingroup$ 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. $\endgroup$ Sep 16 '19 at 5:03
  • $\begingroup$ @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$. $\endgroup$
    – bnoite
    Sep 16 '19 at 5:14
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ God, I feel so dumb not noticing I could split it into two cases. Thank you! $\endgroup$
    – bnoite
    Sep 16 '19 at 5:27
  • $\begingroup$ @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) $\endgroup$ Sep 16 '19 at 5:30
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bnoite
    Sep 16 '19 at 5:20
  • $\begingroup$ $\log_2\frac23\lt0$. So your inequality flips. $\endgroup$
    – user403337
    Sep 16 '19 at 6:16
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.