Proof. Lemma Let integers $a$ and real number $z$ satisfy $|a| \ge 2$. For any non-negative integer $n$, if
$$||a^n z|| < \frac{1}{|a| + 1},$$
then $z$ is an integer. Here, $||x||$ is defined as the distance between the real number $x$ and the nearest integer, that is, $||x|| = \min(\{x\}, 1 - \{x\})$.

Proof of the lemma: Without loss of generality, assume $a \ge 2$ (otherwise, replace $a$ with $-a$). Suppose the conclusion is false. Without loss of generality, assume $0 < z \le \frac{1}{2}$ (otherwise, replace $z$ with $m \mp z$, where $m$ is some suitable integer).
Since $z \in (0, \frac{1}{a^{-1}(a+1)})$, we can assume that
$$\frac{1}{a^k(a+1)} \le z < \frac{1}{a^{k-1}(a+1)} \quad (k \in \mathbb{Z}_{\ge 0}),$$
which implies $\frac{1}{a+1} \le a^k z < 1 - \frac{1}{a+1}$. Consequently, $||a^k z|| \ge \frac{1}{a+1}$, leading to a contradiction. Thus, the lemma is proven.

Back to the original question. Assume, for the sake of contradiction, that $f(x) = a_d x^d + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$ is not a polynomial with rational coefficients. Let $t$ be the largest index such that $a_t \notin \mathbb{Q}$. Define
$$\left\{ \frac{f(n)a^n}{b} \right\} = \frac{r_n + \varepsilon_n}{b}, \quad \varepsilon_n \in [0, 1).$$
Let $g(x) = \Delta^t f(x) = \sum_{i=0}^{t} (-1)^i \binom{t}{i} f(x + t - i)$, where $\Delta$ denotes the finite difference operator. It is easy to see that except for the constant term, all coefficients of $g(x)$ are rational numbers. Let $g(x) = c_{d-t}x^{d-t} + \cdots + c_1x + c_0$, and let $K$ be the least common multiple of the denominators of $c_1, c_2, \cdots, c_{d-t}$. Now,
$$\left\{ \frac{g(n)a^{n+t}}{b} \right\} = \left\{ \sum_{i=0}^{t} \frac{(-1)^i \binom{t}{i} f(n+t-i) a^{n+t-i} \cdot a^i}{b} \right\} \\ = \left\{ \sum_{i=0}^{t} \frac{(-1)^i \binom{t}{i} a^i (r_{n+t-i} + \varepsilon_{n+t-i})}{b} \right\} \\ = \left\{ \sum_{i=0}^{t} r_{n+t-i} \frac{(-1)^i \binom{t}{i} a^i}{b} + \sum_{i=0}^{t} \varepsilon_{n+t-i} \frac{(-1)^i \binom{t}{i}}{b} \right\}.$$

Let $\delta_n = \sum_{i=0}^{t} \varepsilon_{n+t-i} \cdot \frac{(-1)^i \binom{t}{i} a^i}{b}$. Note that
$$\sum_{i=0}^{t} \left| \frac{(-1)^i \binom{t}{i} a^i}{b} \right| = \sum_{i=0}^{t} \frac{\binom{t}{i} |a|^i}{b} = \frac{(|a|+1)^t}{b} \le \frac{(|a|+1)^d}{b} \le \frac{1}{|a|+1},$$
which implies that for any positive integers $n$ and $n'$,
$$\left| \delta_n - \delta_{n'} \right| \le \sum_{i=0}^{t} \left| \varepsilon_{n+t-i} - \varepsilon_{n'+t-i} \right| \cdot \frac{\binom{t}{i} |a|^i}{b} < \sum_{i=0}^{t} \frac{\binom{t}{i} |a|^i}{b} \le \frac{1}{|a|+1}.$$
We choose positive integers $M$ and $n$ such that $M$ is a multiple of the smallest positive period of $\{r_n\}$ and $bK|M$, and when $n \ge n_0$, we have $bK|a^{n+M+t} - a^{n+t}$. Then, for $n \ge n_0$,
$$\left\| \frac{g(n+M)a^{n+M+t}}{b} - \frac{g(n)a^{n+t}}{b} \right\| = \left\| \delta_{n+M} - \delta_n \right\| < \frac{1}{|a|+1},$$
where the first equality holds because $r_{n+M+t-i} = r_{n+t-i}$ for $i = 0, 1, \dots, t$. On the other hand,
$$\begin{aligned} & \left| \frac{g(n+M)a^{n+M+t}}{b} - \frac{g(n)a^{n+t}}{b} \right| \\ &= \left| \frac{c_0}{b} (a^{n+M+t} - a^{n+t}) + \sum_{i=1}^{d-t} \frac{c_i}{b} ((n+M)^i a^{n+M+t} - n^i a^{n+t}) \right| \\ &= \left| \frac{c_0(a^M - 1)a^{n_0+t}}{b} \cdot a^{n-n_0} \right|. \end{aligned}$$
According to the lemma, we have $\frac{c_0(a^M - 1)a^{n_0+t}}{b} \in \mathbb{Z}$, but this contradicts the irrationality of $c_0$! Hence, the proof is complete. $\square$