# Function that grows faster than any function in a given (perhaps infinite) set

I am self studying point set topology with MAT327 from Toronto University. In the topic of countability (chapter 4), I am asked to: "given a fixed set of functions $$f_n:\mathbb{N}\rightarrow\mathbb{N}$$, $$n\in\mathbb{N}$$ construct a function $$g: \mathbb{N}\rightarrow\mathbb{N}$$ that grows faster than all $$f_n$$"

this is: $$\lim_{k\rightarrow\infty}\frac{g(k)}{f_n(k)}= \infty$$

In the course is assumed that $$0\not\in\mathbb{N}$$. If the set of functions $$f_n$$ were finite $$g(k)=\Pi_nf(k)^{f(k)}$$ would be a solution, but I am not sure I can use this trick for an infinite set of functions.

How can I construct a function than grows faster than a given (infinite) set of functions?

• What definition of "growth" do you use? As in big-O? Also your $g$ is not necessarily growing strictly faster than all $f_n$ in finite case, e.g. if all $f_n$ are constant, then so is your $g$. Jul 5 at 12:32
• @freakish Edited the question to define growth. Thanks for noticing the caveat for constant f_n. I take your comment as a solution. Thx Jul 5 at 12:41

Your $$g(k)=\prod_{n} f_n(k)^{f_n(k)}$$ does not necessarily work even in finite case. For example when all $$f_n$$ are constant then so is $$g$$.
$$g(k)=k\cdot\max_{j\leq k}\{f_j(k)\}$$
Indeed, for any fixed $$n$$ we have
$$\lim_{k\to\infty}\frac{g(k)}{f_n(k)}=\lim_{k\to\infty}\frac{k\cdot\max_{j\leq k}\{f_j(k)\}}{f_n(k)}$$
Now given $$k\geq n$$ we have $$\frac{k\cdot\max_{j\leq k}\{f_j(k)\}}{f_n(k)}\geq\frac{k\cdot f_n(k)}{f_n(k)}=k\to\infty$$