Prove that $3^n$ is not $O(2^n)$. I am working on some Big oh questions and I can't seem to get how disprove them. In this case we have:
Prove that $3^n$ is not $O(2^n)$
I can see that its obvious just by looking at the two functions, but I don't know how to prove it. What are the steps one should take to approach to disprove something like this?
Thanks
 A: What you want to argue is that there does not exist an $M$ such that $3^n \le M 2^n$ for all $n$ sufficiently large. Suppose such an $M$ existed. Then you would have that $\left(\dfrac{3}{2}\right)^n \le M$. Can you see how to proceed?
A: Assume that $3^n \in O(2^n)$. Then exists constant $C \in \mathbb{R}$ and $n_0 \in \mathbb{N}$, that:
$$\forall n>n_0 \; 3^n \leq 2^nC$$
But it's equal:
$$\forall n>n_0 \; (\frac{3}{2})^n \leq C$$
It isn't true, because $\lim_{n \to \infty}(\frac{3}{2})^n=\infty$.
A: $a(n)=O(b(n))$ means that there is a bounded function $f$ such that $a(n)=f(n)b(n)$. So if you prove that $\displaystyle{\frac{3^n}{2^n}}$, you are done.
Now, 
$$\frac{3^n}{2^n}=\left(\frac{3}{2}\right)^n$$
And $\frac32=1.5>1$. Can you conclude? It may be more obvious if you notice that
$$\left(\frac{3}{2}\right)^{2n}=\left(\frac{9}{4}\right)^{n}>2^n$$
A: You want to show that for every c, there exists $k$ such that $3^{n} > 2^{n}c$ when $n > k$.
Let $c$ be fixed, then as long as $\frac{3}{2}^n > c$ i.e. $n >= k > \frac{\ln{c}}{\ln(\frac{3}{2})}$. Since this exists for all $c>0$ we have that $3^{n}$ is not the same order as $2^{n}$.
