Question

Given f(n) = o(g(n)), prove that 2^f(n) = o(2^g(n))

Answer 1

lim(F/G)=C <- lim(f/g)=C

Answer 2

f(n) = o(g(n)) means 0<= f(n) < g(n) for all n>= n0

as f(n) is always less than g(n) and both are positive

2^f(n) < c. 2^g(n) for all n >= n0 and c is a constant

Therefore we can say that 2^f(n) = o (2^g(n)) when f(n) = o(g(n))

Answer 3

f(n)=o(g(n)), so we have

for any arbitrarily small c we can find a N, s.t. ALL n>N  f(n)<cg(n).

2^n grows strictly with n. so we have

2^f(n)<2^(cg(n)), 2^f(n)<(2^g(n))^c.

we find another arbitrarily small number w, then we must have

2^f(n)<w*((2^g(n))^c/w).

We just need to prove that with an large number M found s.t. ALL n>M  (2^g(n))^c/w<2^g(n).

substitute x=2^g(n). when n is large enough, it is the same with x.

we just need to prove that for arbitrarily small w and c we can find a X  s.t. ALL x>X   x^c<x*w.

X^(c-1)<w, s.t. X^(1-c)>1/w, X>(1/w)^(1/(1-c)).

We can find such a X, so we can find such a M. s.t. ALL n>M

 2^f(n)<w*((2^g(n))^c/w)<w*2^g(n), for arbitrarily small w and c.

this is the definition of small o.

So we have 2^f(n)=o(2^g(n)).

Q.E.D.

Answer 4

f(n) = o(g(n)) ==> f(n) < c g(n) - m for any constant m, any c>0 and n>n₀ 

when c =1, f(n) < g(n) - m for all n>n₀

Need to prove: 2^f(n) < a 2^g(n) for any a>0 and all n>n₀'

if a >= 1, it's obvious 2^f(n) < a 2^g(n) for all n>n₀

if 0 < a < 1, let b = 1/a; b > 1,

for n>n₀ (this means n₀' >= n₀) , we can reason backward like this:

2^f(n) < a 2^g(n) 2^f(n)  <==  2^f(n) < (1/b) 2^g(n)  <== 2^f(n) < 2^log(1/b) 2^g(n)  <==

2^f(n) < 2^(g(n) - logb)  <==  f(n) < g(n) - logb which is proven at the beginning, where m could be logb.

PS: "f(n) = o(g(n)) ==> f(n) < c g(n) - m" this is straightforward and can be easily proven by L' Hopital's Rule.

Answer 5

now f(n) = o(g(n))

lim n->infinity (f(n)/g(n)) = 0

lim n->infinity (2^f(n)/2^g(n)) =  lim n->infinity (2^(f(n) - g(n)))

                                              = lim n->infinity (2^(f(n) - g(n)))

                                              = lim n->infinity (1/(2^(g(n)*(1-f(n)/g(n)))))

cuz lim n->infinity (f(n)/g(n)) = 0

lim n->infinity (2^f(n)/2^g(n)) = lim n->infinity (1/2^g(n))

if g(n) -> infinity for n -> infinity

lim n->infinity (2^f(n)/2^g(n)) = 0

as a result 2^f(n) = o(2^g(n))

else

it is not necessary that 2^f(n) = o(2^g(n))

Comments

Hi Dongxing, why other condition is unnecessary? For example, f(n)->0, g(n)->0, lim n->infinity(f(n)/g(n))=0.

---

Hi Taoran
I am sorry that I don't get what u express
However, let's assume that f(n) = 1/n^2 g(n) = 1/n  then f(n) = o(g(n))right?
Maybe you will find the limit of 2^(f(n)-g(n)) is 1.

---

But the limit should be zero according to the small o definition, right?