I know that in general does not exist a countable basis for functions in the form $f : \mathbb{N} \rightarrow \mathbb{N}$. But if I restrict to the functions $f(k) = (k)_n$, for fixed $n = 0, 1, 2, \dots$ and $k \in \mathbb{N}$ and where $(k)_n$ represents the falling factorial polynomial, can I find a basis?
Thanks to everyone.
Let $f_n:\mathbb N\to\mathbb N$ be the function $f_n(k)=(k)_n=\prod_{l=0}^{n-1}(k-l)$, which is a polynomial of degree $n$. Therefore the functions $\{f_n\}_{n\in\mathbb N}$ already are linearly independent, which means they are a basis of the space they span. A simpler basis is given by the functions $g_n(k):=k^n$ (you can show inductively over $n$ that each $g_n\in\operatorname{span}(f_0,\ldots,f_n)$).