Does a polynomial-like thing from $\mathbb N\to \mathbb N$ always has coefficients in the rationals $\mathbb Q$? If $f(n) = a_k(n) n^k+\dots+a_1(n)n+a_0(n)$ is a function $\mathbb N\to \mathbb N$ with $a_1,\dots, a_k\colon\mathbb N\to\mathbb R$ does it follow that these functions $a_i$ are functions $\mathbb N\to \mathbb Q$, by which I mean that they just take rational values?
 A: The answer is 'No'. Generalizing @dxiv's comment:
Let $g$ be an arbitrary function $\mathbb{N} \rightarrow \mathbb{N}$, and $a_0, a_1, ... a_{k-1}$ be arbitrary functions $\mathbb{N} \rightarrow \mathbb{R}$.  
Define
$$ a_k(n) = \frac{ g(n) - a_0(n) - a_1(n)n .... - a_{k-1}(n)n^{k-1}}{n^k}$$
Then if you plug $a_0, a_1 ... a_k$ into your formula defining $f(n)$ you get $f$ is your arbitrary function $g$. 
So no matter what your $\mathbb{N} \rightarrow \mathbb{N}$ function is, you can let your $\{a_i(n)\}_{i=0}^{k-1}$ be $\sin(n)$, $e^n$, or any other ugly transcendental functions, and you can still express your original function in the manner you asked.
(There is some complication with that definition of $a_k$ at $n = 0$, but so long as $g(0) = a_0(0)$ we can let the value of $a_k$ at $0$ be arbitrary and everything still works.)
A: Not necessasarily. Let, $n=1$, and $a_1(1)=\sqrt{2}$ and $a_2(1)=-\sqrt{2}$, while, $a_i(1) \in \mathbb{N}$ for $i \neq 1,2$ and $a_i(n) \in \mathbb{N}$ for $n \neq 1$ for simplicity. Then, still $f(1) \in \mathbb{N}$.
