Function growing faster than a sequence of functions

1. Jan 6, 2010

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?

2. Jan 6, 2010

Landau

Do you know anything about the f_k's?

3. Jan 7, 2010

simeonsen_bg

f_k are arbitrary functions from the naturals into itself.

4. Jan 11, 2010

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 continous extension. Then I would use the fact that polynomails are dense in the set of continous 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 continous function (by saying suppose g is a maximum continous function, then consider g + 1, kind of thing). So if I was given an continous 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.

Last edited: Jan 11, 2010