Is there an example of a rational polynomial that has integer output for all integer inputs that are sufficiently large? Is there an example of a rational polynomial $f(n)\in \mathbb{Q}[t]$ that has integer output for all integer inputs that are sufficiently large, but not for, say, inputs $n=1,2,3,\dots,n$?
 A: No. If $f$ has degree $d$, you can reconstruct $f(n-1)$ from $f(n), \ldots, f(n+d)$ by taking repeated differences and adding again.
A: No. 
Suppose $f$ is a polynomial in $\mathbb{Q}[x]$ outputting integers for sufficiently large integer inputs. Then I claim $f$ can be written
$$
\sum_{i = 0}^n a_i {x \choose i}
$$
where
$$
{x \choose i} = \frac{x(x-1)\ldots(x-i+1)}{i!}
$$
and the $a_i$ are integers; note that this expression is $1$ when $i = 0$ (because the numerator is the empty product). This claim then proves your result, since clearly anything that can be written this way has your property.
The proof: Clearly we can write $f$ this way for some rational numbers $a_i$. We will recover the $a_i$ and then argue that they must be integers. If $g$ is a polynomial, set
$$
\Delta g = g(x+1) - g(x).
$$
We compute (just by writing it out) that
$$
\Delta {x \choose i} = {x \choose i -1}
$$
for $i > 0$ and clearly $\Delta {x \choose 0} = 0$.
Since $\Delta$ is linear, it follows that 
\begin{align*}
a_0 =& f(0) & \\
a_1 =& (\Delta f)(0)\\
a_2 =& (\Delta^{(2)} f)(0)\\
\ldots \\
a_n =& (\Delta^{(n)}f)(0)\\
\end{align*}
With these formulas and induction on the degree of $f$, we have that all of the coefficients but $a_0$ must be integers (because the polynomials $\Delta^{(i)}(f)$ have smaller degree, they must evaluate to integers on all integers). But then $a_0$ must be an integer as well, since when you plug in a large number you will get an integer plus $a_0$.
A: Any $P\in\mathbb Q[X]$ whose evaluations at all $n \in\Bbb N$ are in $\Bbb Z$ are integer linear combinations of the rational polynomials $\binom Xd$ with $d \in\Bbb N$: the coefficient of $\tbinom X0=1$ is the evaluation $P$ at $0$; subtracting off that (constant) term, the coefficient of $\tbinom X1=X$ is the evaluation at $1$ of the remainder; subtracting off that (linear) term, the coefficient of $\tbinom X2=\frac{X^2-X}2$ is the evaluation at $2$ of the remainder; and so forth. The remainder ultimately becomes $0$ when the coefficient of $\binom Xd$ is taken into account where $d=\deg P$, as we have subtracted off a polynomial $Q$ of degree $d$ whose evaluations in $0,1,\ldots,d$ coincide with those of $P$, which forces $P=Q$.
Now the rational polynomials $\tbinom Xd$ take integer values at all $n\in\Bbb Z$, and therefore so will $P$. If for some $P'\in\mathbb Q[X]$ the evaluations at all integers${}\geq n_0$ are in $\Bbb Z$, then consider $P=P'[X:=X+n_0]$ (substitute $X+n_0$ for $X$), now $P$ has integer evaluations at all $n \in\Bbb N$, and the above applies, so $P'$ has integer evaluations at all $n \in\Bbb Z$.
To make the link with answer by Hagen von Eitzen, this argument only needs the integrality at $\deg P+1$ successive values, which forces all evaluations to be integer.
