Proving that $f(n) = o(g(n))$ implies $2^{f(n)} = o(2^{g(n)})$

Question

I can't find a counterexample to $$f(n) = o(g(n)) \text{ implies } 2^{f(n)} = o(2^{g(n)})\,,$$ but I do not know a formal way of proving it. Can anyone lead me in the right direction? I asked this exact question yesterday in Stack Overflow by accident (meant to post here) but no one could come up with a valid way of approaching this question.

This is "little-$o$" notation by the way. So a strict upper bound It should be for monotonically increasing functions

Answer 1

Hint:

We want to prove $2^{f(n)} = o(2^{g(n)})$. This is equivalent to $\lim_{n\to\infty} \dfrac{2^{f(n)}}{2^{g(n)}} = 0$. We can rewrite the expression inside the limit as $2^{f(n)-g(n)}$, and, exploiting the hypothesis $f(n) = o(g(n))$, we have $\lim_{n\to\infty} f(n)-g(n) = \cdots$

Answer 2

Firstly, let's establish the definition for little-o:

$f(n) = o(g(n))$ if and only if $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0$

• Firstly, about counterexample. Take $f(n) = \frac{1}{n^2}$ and $g(n) = \frac{1}{n}$. The ratio is $\frac{f(n)}{g(n)} = \frac{\frac{1}{n^2}}{\frac{1}{n}} = \frac{1}{n} \to 0$, so $f(n) = o(g(n))$. However, $\frac{2^{f(n)}}{2^{g(n)}} = 2^{f(n) - g(n)} = 2^{\left(\frac{1}{n^2} - \frac{1}{n}\right)} \to 1$, because $\frac{1}{n^2} - \frac{1}{n} \to 0$ when $n \to \infty$, so the conclusion given is not correct.
• Secondly, let's see the formality so we know from where this counterexample comes and what additional conditions might support the claim.

Recall, that if $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0$ then by definition of the limit $\forall \epsilon > 0 \exists N\forall n \geq N : \left|\frac{f(n)}{g(n)}\right| \leq \epsilon$. From this immediately we get $\left|{f(n)}\right| \leq \epsilon\left|{g(n)}\right|$. After subtracting $g(n)$ and adding for example positiveness (don't want to dig into all cases) we get something like $f(n) - g(n) \leq (\epsilon-1) g(n)$. The conclusion I have taken from here is that the claim might be true only if $g(n) \to \infty$. And that's exactly from where I took the counterexample.

Update 1

For those who ask what about monotonicity: Still take $g(n)$ any function with limit not infinity, for example $\arctan(x)$, $f(n) = \frac{g(n)}{n}$. By definition $f(n) = o(g(n))$. The difference $f(n) - g(n) \to 0 - \frac{\pi}{2} \neq -\infty$ so powers are not related as little-o.

Update 2

For both increasing $f$ and $g$ you can revert the counterexample $f(n) = -1/n^2$ and $g(n) = -1/n$.

If you put the requirement, that starting from some $n$ we have $f(n) > 0$ and $g(n) > 0$, the following is true. Assume $g(n) \not\to \infty$, that is $g(n) \to C \geq 0$. Then $f(n) = \alpha_n g(n)$ where $\alpha_n \to 0$ so $f(n) \to 0$. But $f(n) > 0$ and thus must be decreasing at some point which violates the monotinicity requirement. By contradiction, $g(n) \to \infty$.

Take $\epsilon = \frac{1}{2}$ in the above, you have $f(n) - g(n) \leq -0.5 g(n) \to -\infty$ which proofs the claim.