Function growing faster than a sequence of functions

[simeonsen_bg]

Hi, I have a sequence f_k(n) of functions N-->N, k=1,2... and I need to find a function f(n) growing faster than any f_k, i.e.

f_k(n)/f(n) --> 0 as n-->infinity for any k.

Is it possible and how can it be done?

 

[Landau]

Do you know anything about the f_k's?

 

[simeonsen_bg]

f_k are arbitrary functions from the naturals into itself.

 

[breedencm]

Ok, i realized that the following is wrong;

I'm pretty sure that it's not possible. I would first claim that for any function f: N -> N has a continuous extension. Then I would use the fact that polynomails are dense in the set of continuous functions on R. Since the set of polynomals are countable, I would construct a sequence of all polynomails. Then I would go to claim that there is no maximum continuous function (by saying suppose g is a maximum continuous function, then consider g + 1, kind of thing). So if I was given an continuous function, I would consider g + 1, and then find a polynomial that represents it arbitrarily close (at least with in 1/2 distance) and claim that g is indeed not a function that bounds my sequence of functions.

Ok. So now we've shown that in general it's impossible. However, if you add "poitwise bounded" as an assumption, then it is possible.