Disproving big O In the question, we are to assume that f(n) is O(g(n)). Next, we have to decide whether 2^f(n) is O(2^g(n)). According, to some solutions on the internet, this can be proven to be false if we take f(n)=2n and g(n)=n. However, I'm not able to completely derive the proof to backup the premise that it is false.

Here's what I have thus far: Suppose we take f(n)=2n and g(n)=n.  We
  know that f(n)≤ C*g(n)  for C>0 and ∀ n≥n0≥0. After substituting and
  raising both sides to base 2, we get: 2^(2n)≤2^(c*n)≡4^n≤2^(c*n)...

Here's where I'm stuck. What I'm trying to do is as follows: for all n0 and C, I'm trying to find an n>=n0 such that 2^f(n) > 2^(c*g(n)). How should I proceed?
 A: You write:

Suppose we take $f(n)=2n$ and $g(n)=n$. We know that $f(n)\le Cg(n)$ for $C>0$ and $\forall n\ge n_0\ge 0$.

You don’t know this unless you specify $C$ and $n_0$. For example, if you set $C=1$, it’s simply false, no matter what $n_0$ you choose: $2n$ is not less than or equal to $n$.
However, if we set $C=2$ and $n_0=0$, we get a true statement: it is indeed the case that $2n\le2n$ for all $n\ge 0$. The fact that we can find $C$ and $n_0$ making this true is what tells us that $2n$ is $O(n)$.
Now you want to show that $2^{2n}$ is not $O(2^n)$. Suppose that it were; then by definition there would be $C>0$ and $n_0>0$ such that $2^{2n}\le C\cdot2^n$ for all $n\ge n_0$. What does it mean to have $2^{2n}\le C\cdot 2^n$ for all $n\ge n_0$? That would tell us that $\dfrac{2^{2n}}{2^n}\le C$ for all $n\ge n_0$. But $\dfrac{2^{2n}}{2^n}=2^{2n-n}=2^n$, so we’d have constants $C>0$ and $n_0\ge 0$ such that $2^n\le C$ for all $n\ge n_0$. Is that actually possible? What happens to $2^n$ as $n$ increases?
A: Certainly $2n=O(n)$. To show that $2^{2n}$ is not $O(2^n)$, informally we want to show that in the long run $2^{2n}$ grows much faster than $2^n$. More formally,  we need to show that for any $N$, and any fixed constant $c$, there exists $n \gt N$ such that $2^{2n}\gt c2^n$. 
For any $N$, choose $n \gt N$ such that $2^n \gt c$. Then $2^{2n}=(2^n)^2\gt c2^n$. 
