Prove that $3^n$ is not $O(2^n)$ I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$.
To prove  $3^n \in O(2^n)$, we must find $n_0$, $c$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.
$$
\begin{aligned}
3^n &\leq c \cdot 2^n\\
\left(\frac{3}{2}\right)^n& \leq c
\end{aligned}
$$
I am stuck here....
I could use a log here, but I don't see the use
Any hint?
UPDATE
$$
\begin{aligned}
3^n &\geq c \cdot 2^n\\
\left(\frac{3}{2}\right)^n& \geq c\\
n \log(3/2) &\geq \frac{\log c}{\log 3/2}\\
n &\geq \log \frac{2c}{3}
\end{aligned}
$$
For every $n \geq \log \frac{2c}{3}$, $3^n \geq 2^n$. Therefore, $3^n$ is not $O(2^n)$.
 A: Your goal is to prove that no value of $c$ can work.
One way of doing so is to show that the equation $(3/2)^n \geq c$ has infinitely many solutions for $n$. Do you see why that is?
A: You have to prove this is not the case. Let's first rearrange your definition of $O(2^n)$ a little:
$f$ is $O(2^n)$ if there exist $n_0$ and $C$ such that, for any $n\geq n_0$, $f(n) \leq C\, 2^n$.
Now, work out carefully what it means to say $3^n$ is not $O(2^n)$: 
$f$ is not $O(2^n)$ if, for every $n_0$ and $C$, there exists $n \geq n_0$ such that $f(n) > C \, 2^n$. 
So, if I hand you any $C$ and $n_0$, you have to find $n \geq n_0$ so that $3^n > C \,2^n$. If it isn't clear how to prove it yet, try finding an appropriate $n$ if I give you $C = 700$ and $n_0 = 4$, then do the general case.
A: Your idea of taking a logarithm is a good one. $\log (3/2)^n = n\log (3/2)$. That should pretty much finish off your argument, as long as you know logarithms are increasing.
A: Hint By Bernoulli inequality
$$(\frac{3}{2})^n \geq 1+\frac{n}{2}$$
