(From CLRS -- 3-4,d)
Let $f(n)$ and $g(n)$ be asymptotically positive functions.
I tried to prove that $$f(n) = O(g(n)) \implies 2^{f(n)} = O\left(2^{g(n)}\right) .$$
I know that the above statement is false, so where have I gone wrong in my proof?:
Suppose $f(n) = O(g(n)).$ Then there exist positive real numbers $c, n_0$ such that for all $n \geq n_0:$ $$0 \leq f(n) \leq c g(n).$$ Raising all sides to the power of 2, we have: $$0 \leq 2^{f(n)} \leq 2^{cg(n)}$$ (we can do this because $2^n$ is an increasing function).
From this, we can say that $$0 \leq 2^{f(n)} \leq \underbrace{2^c}_{\text{arbitrary constant}}\cdot 2^{g(n)}$$ so if $d = 2^c$, we can say that $2^{f(n)} = O(2^{g(n)})$.
(I now know that $f(n) = 2n, \ \ g(n) = n$ is an easy counterexample, but I'm still struggling to find the flaw in my "proof").