0
$\begingroup$

I really need help solving the following question:

Given: $$f(n) = o(g(n))$$

Prove: $$3^{f(n)} = o(3^{g(n)})$$

My attempt:

I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $.

I need to prove that $f(n) - g(n) \xrightarrow{} -\infty$ so that $3^{f(n)-g(n)} \xrightarrow{} 0$.

How do I prove that?

In general, I'm not sure what properties can I assume about $f$ and $g$. Are they positive? What else do I know about them? Are we assuming that all these function approach $\infty$ or can they be $\frac{1}{n}$ etc.?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ You should direct your questions to whoever set you this exercise. $\endgroup$ – Yuval Filmus Jul 6 '19 at 11:04
  • $\begingroup$ If we assume that $f,g$ take values in the positive integers, then $f = o(g)$ does imply $f - g \to -\infty$. $\endgroup$ – Yuval Filmus Jul 6 '19 at 12:35
  • $\begingroup$ @YuvalFilmus Isn't it necessary to say that both functions approach $\infty$ in order to say that? And if not, how did you deduce it? I'm self studying this and I'm using material from a friend. $\endgroup$ – PhysicsPrincess Jul 6 '19 at 16:12
  • $\begingroup$ Is it actually true that all function that take value in the positive integers approach $\infty$ (I can't come up with one that doesn't) $\endgroup$ – PhysicsPrincess Jul 6 '19 at 16:19
  • $\begingroup$ How about the function $f(n) = 1$? However, if $f = o(g)$ and $f,g$ takes values in the positive integers, then since $f \geq 1$, we must have $g \to \infty$. $\endgroup$ – Yuval Filmus Jul 6 '19 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.