Step 1: Suppose $P$ has degree $d$. Let $Q$ be the polynomial of degree at most $d$ with $Q(x)=q_x$ for $0\leq x\leq d$. Since the $q_x$ are all integers, $Q$ has rational coefficients, and there exists $k$ so that $kQ$ has integer coefficients. Then $m-n|kQ(m)-kQ(n)$ for all $m,n\in \mathbb N_0$. Step 2 We show that $Q$ is the desired polynomial. Let $x>n$ be given. Now \[kq_x\equiv kq_m\pmod{x-m}\text{ for all integers }m\in[0,d]\] Since $kQ(x)$ satisfies these relations as well, and $kq_m=kQ(m)$, \[kq_x\equiv kQ(x)\pmod{x-m}\text{ for all integers }m\in[0,d]\] and hence \[kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1) \] Now \begin{align*} \text{lcm}(x,x-1,\ldots, x-i-1)&=\text{lcm}[\text{lcm}(x,x-1,\ldots, x-i),x-i-1]\\ &=\frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[\text{lcm}(x,x-1,\ldots, x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[x(x-1)\cdots(x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{(i+1)!} \end{align*} so by induction $\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}$. Since $P(x), Q(x)$ have degree $d$, for large enough $x$ (say $x>L$) we have $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. By (1) $kq_x$ must differ by a multiple of $\text{lcm}(x,x-1,\ldots, x-d)$ from $kQ(x)$; hence $q_x$ must differ by a multiple of $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ from $Q(x)$, and for $x>L$ we must have $q_x=Q(x)$. Now for any $y$ we have $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ for any $x>L$. Since $x-y$ can be arbitrarily large, we must have $Q(y)=q_y$, as needed.

Does anyone have a shorter solution?

Nice! We consider the polynomial $f$ of the minimal degree such that $a_n \le f(n)$ for all but finitely many $n$. Let $d$ be the degree of $f$. We consider a polynomial $g$ of degree $d$ such that $g(i)=a_i$ for $1 \le i \le d+1$. By the Lagrange Interpolation formula, this polynomial is of rational coefficients and uniquely defined. Let $N>0$ be a constant such that $h(x)=Ng(x)$ is a polynomial with integer coefficients. We replace the sequence $a_n$ by $b_n=Na_n$. This does not affect our divisibility relation and the other conditions are scaled accordingly. Choose $m$ sufficiently large, in particular $m>c$ where $c>0$ is a constant we shall disclose later in the proof. Now, we have \begin{align*} m-i \mid (b_m-b_i)-(h(m)-h(i)) = (b_m-h(m)) \end{align*}where $1 \le i \le d+1$. Therefore, we have the relation: \begin{align*} \operatorname{lcm}(m-1,\dots, m-d, m-d-1) \mid |b_m-h(m)| \end{align*}and we observe that $|b_m-h(m)|_{m \ge 1}$ is bounded above by a polynomial of degree $d$, i.e., there exists a constant $a>0$ such that $|b_m-h(m)| \le am^d$. However, we see that the relation \begin{align*} x_1\cdot \dots \cdot x_k \mid \operatorname{lcm}(x_1,\dots, x_k)\cdot \Pi \gcd (x_i,x_j) \end{align*}holds for all integers $x_1,\dots, x_k$, where in the last product the gcd is taken over all pairs $1 \le i < j \le k$. This result is established by comparing the $v_p$'s on each side. Now, this directly translates into an inequality $A \le B$ if $A \mid B$. Notice that $\gcd (a,b) \le |a-b|$. Therefore, we have \begin{align*} am^d \ge \operatorname{lcm}(m-1,...,m-d-1) \ge \frac{(m-1)\cdot \dots \cdot (m-d-1)}{\Pi_{1 \le i<j \le d+1} \gcd(m-i,m-j)} \ge \frac{(m-1)\cdot \dots \cdot (m-d-1)}{\Pi_{1 \le i < j \le d+1} (j-i)}=O(m^{d+1}), \end{align*}yielding a contradiction for all sufficiently large $m$, unless $b_m=h(m)$. We deduce that $b_m=h(m)$ for all sufficiently large $m$, i.e., for all $m>M$ for some constant $M>0$. Now, we take $n \le M$ and notice that $m-n \mid b_m-b_n$ implies that $m-n \mid |b_n-h(n)|$ which further yields, due to the size of $m$, that $b_n=h(n)$. In summary, we conclude from the above deductions that $b_n=h(n)$ for all $n \in \mathbb{N}$ and so, $a_n=g(n)$ for all $n \in \mathbb{N}$. The result follows. Comment The result is sharp, namely, we cannot reduce it to showing that $g \in \mathbb{Z}[X]$. A counter example can be the sequence $a_n=\binom{n}{2}+2016$ which clearly, satisfies all our conditions but is not in $\mathbb{Z}[X]$.

Let $d=\deg P$. Let $Q(x)$ be the unique polynomial with degree at most $d$ such that $Q(x)=q_x$ for all $0\le x\le d$. It exists because we can set up a system of $d+1$ variables and linear equations, and the solution exists and is unique because the Vandermonde determinant is nonzero. This also shows that $H$ has rational coefficients. Pick $k\in\mathbb{Z}$ such that $H=kQ\in\mathbb{Z}[x]$, and let $a_n=kq_n$. It now suffices to show that $a_n=H(n)$ for all $n\ge 0$, where we know that $H(n)=n$ for all $0\le n\le d$, $\deg H\le d$, and $m-n\mid a_m-a_n$ for all $m\not=n$. Suppose $n\ge d+1$. Then, we have that \begin{align*} a_n &\equiv a_0 = H(0)\pmod{n} \\ a_n &\equiv a_1 = H(1)\pmod{n-1} \\ &\vdots \\ a_n &\equiv a_d = H(d) \pmod{n-d}. \end{align*}By the Chinese Remainder Theorem, this has a unique solution $\pmod{f(n)}$ where $f(n):=\mathrm{lcm}(n-d,n-d+1,\ldots,n-1,n)$. Note that one solution that definitely works is $H(n)$ since $H\in\mathbb{Z}[x]$. Thus, $a_n\equiv H(n)\pmod{f(n)}$. The key point is that $n^{d+1}/f(n)$ is bounded above by some constant that only depends on $n$ (I think something like $d\cdot (d-1)^2\cdots 2^{d-1}$ works), so in particular, $f(n)$ grows faster than $P(n)$. Eventually then, we must have $f(n)>100k P(n)$, and since $|a_n|<k P(n)$ and $a_n\equiv H(n)\pmod{f(n)}$, we see that $a_n=H(n)$ for sufficiently large $n$. So $a_n=H(n)$ for all $n\ge N$. It remains to show that $a_n=H(n)$ for all $n<N$. We see that $a_n\equiv a_m=H(m)\equiv H(n)\pmod{m-n}$ for all $m\ge N$, so by taking $m$ to be sufficiently large, we learn that $a_n=H(n)$, as desired. Dividing by $k$, we get that $q_n=Q(n)$ for all $n$.

For those interested, here is a massive generalization (posted today!)

Let \(d\) be the degree of \(P\), and let \(Q\) be the (unique) rational polynomial with \(Q(i)=q_i\) for \(i=0,\ldots,d\). Appropriately scale up everything so that \(Q\) has integer coefficients. Lemma: For all \(d\), \[\operatorname{lcm}(n,n-1,\ldots,n-d)=O\big(n^{d+1}\big).\] Proof. Evidently \(\operatorname{lcm}(n,n-1,\ldots,n-d)\le n(n-1)\cdots(n-d)=O\big(n^{d+1}\big)\). The lower bound can be attained easily via basically any bound; for instance, \[\operatorname{lcm}(n,\ldots,n-d)\ge\frac{n(n-1)\cdots(n-d)}{\prod_{i<j}\gcd(n-i,n-j)}\ge\frac{n(n-1)\cdots(n-d)}{\prod_{i<j}(j-i)}=O\big(n^{d+1}\big).\]\(\blacksquare\) Claim: For sufficiently large \(n\), we have \(q_n=Q(n)\). Proof. We must have \(q_n\equiv q_i=Q(i)\equiv Q(n)\pmod{n-i}\) for \(i=0,\ldots,d\), so \[q_n\equiv Q(n)\pmod{\operatorname{lcm}(n,\ldots,n-d)}.\]If \(q_n\ne Q(n)\), then for some nonzero \(k\) we have \(q_n=Q(n)+k\operatorname{lcm}(n,\ldots,n-d)=O\big(n^{d+1}\big)\), which will exceed \(P(n)\) in absolute value for sufficiently large \(n\). \(\blacksquare\) To finish the proof, observe that for every \(m\), we have \(q_m\equiv q_n=Q(n)\equiv Q(m)\pmod{n-m}\) for sufficiently large \(n\). By taking \(n\) large, \(q_m=Q(m)\), as needed.

Let $P$ have degree $k$. Let the polynomial $Q$ of minimal degree such that $Q(i)=q_i$ for each $0\le i\le k$ be $Q^*$. Note that $Q^*$ is a rational polynomial with degree at most $k$. Let $d\in\mathbb{Z}_{>0}$ be minimal with $dQ^*\in\mathbb{Z}[x]$. Define $p_i=dq_i$ for each $i$ and note the $p_i$ satisfy the same properties as the $q_i$ by considering $P'=dP(n)$, and moreover the minimal polynomial of $p_0,\dots,p_k$ is an integer polynomial $\tilde{Q}$. Now, consider $n>k$. Observe that we must have $\tilde{Q}(n)\equiv p_n\pmod{n-i}$ for each $0\le i\le k$ because of the condition and the fact that $\tilde{Q}$ is an integer polynomial. Note that any $n-i,n-j$ have common divisor dividing $k!$, hence we can write \[n\cdot \binom{n}{k} \mid \tilde{Q}(n)-p_n.\]For large values of $n$, $|\tilde{Q}(n)+ an\cdot \binom{n}{k}|>10|P(n)|$ for all $a\ne0$ so $p_n=\tilde{Q}(n)$. Now, use large $n$ to uniquely determine every value of $p_i$ for which the previous argument does not work, and note that $p_i=\tilde{Q}(i)$ is the only feasible solution $p_i$ to the modular equations we get. Hence, $q_n=Q^*(n)$ for each $n$, as desired.

MithsApprentice wrote: Suppose $\, q_{0}, \, q_{1}, \, q_{2}, \ldots \; \,$ is an infinite sequence of integers satisfying the following two conditions: (i) $\, m-n \,$ divides $\, q_{m}-q_{n}\,$ for $\, m > n \geq 0,$ (ii) there is a polynomial $\, P \,$ such that $\, |q_{n}| < P(n) \,$ for all $\, n$ Prove that there is a polynomial $\, Q \,$ such that $\, q_{n}= Q(n) \,$ for all $\, n$. Suppose $\text{deg} \ P = d$. Then let by Lagrange Interpolation formula, there exists $Q \in \mathbb{Q}[x]$ of degree $d$ such that $Q(i) = q_i$ for $0 \le i \le d$. For now, we alter $q_i \to kq_i$, $P \to kP = P'$ and $Q \to kQ = Q'$ such that $Q' \in \mathbb{Z}[x]$, and the problem is still true. We wll know prove that $Q'$ satisfies the requirement of the problem. Fix an integer $\ell > d$. Notice that we have \[ \ell - i \mid kq_{\ell} - kq_i, \ \forall 0 \le i \le d \]and since $Q'(i) = kq_i$ for $0 \le i \le d$, we have $\ell - i \mid kq_{\ell} - Q'(i)$. But since $Q' \in \mathbb{Z}[x]$, we have $\ell - i \mid Q'(\ell) - Q'(i)$, which forces \[ \ell - i \mid kq_{\ell} - Q'(\ell) \ \text{for } 0 \le i \le d \]This forces \[ \text{lcm} ( \ell, \ell - 1, \dots, \ell - d) \mid kq_{\ell} - Q'(\ell) \]Claim. $\text{lcm}(\ell, \ell - 1, \dots, \ell - d) = O(\ell^{d + 1})$. Proof. We know that $\text{lcm}(\ell, \ell - 1, \dots, \ell - d) \le \ell(\ell - 1) \dots (\ell - d) = O(\ell^{d + 1})$, and the lower bound is attained by \[ \text{lcm}(\ell, \dots, \ell - d) \ge \frac{\ell(\ell - 1)\dots (\ell - d)}{\prod_{i < j} \gcd(\ell - i, \ell - j)} \ge \frac{\ell(\ell - 1) \dots (\ell - d)}{\prod_{i <j} \gcd(i,j)} = O(\ell^{d + 1}) \] Claim. $Q'(n) = kq_n$ for all sufficiently large integer $n$. Proof. From the condition of the problem, we have $|kq_n| < P'(n)$ for all $n \in \mathbb{N}$. So, $kq_{\ell} - Q'(\ell) \le |Q'(\ell)| + |P'(\ell)|$, and therefore for sufficiently large $n$, if $Q'(n) \not= kq_n$, we must have \[ n(n - 1) \dots (n - d) \le |kq_n - Q'(n)| \le |P'(n)| + |Q'(n)| \]which is a contradiction as $P' + Q'$ is of degree $d$. Claim. $Q'(n) = kq_n$ for all positive integers $n$. Proof. Suppose there exists a positive integer $\ell$ such that $Q'(\ell) \not= kq_{\ell}$. We have \[ n - {\ell} \mid Q'(n) - Q'(\ell) \ \text{and} \ n - \ell \mid kq_n - kq_{\ell} \]for all sufficiently large $n$. Since $kq_n = Q'(n)$ for all sufficiently large $n$, then we must have \[ n - {\ell} \mid Q'(\ell) - kq_{\ell} \]for all sufficiently large $n$. However, this is a contradiction, as we can take $n - \ell > |Q'(\ell) - kq_{\ell}| + 10^{100}$, and we are done. To conclude, we have $kQ(n) = Q'(n) = kq_n$, which forces $Q(n) = q_n$ for all $n \in \mathbb{N}$.

Let $P(x)$ have degree $k$. Suppose that $Q(x)$ is the polynomial of degree $k$ such that $Q(x)=q_x$ for $1\leq{}x\leq{}k$. We now claim that if we fix the first $k$ terms of the sequence $q_i$ such that it satisfies the conditions, the rest of the sequence is fixed. (If it is fixed, it also must be equivalent to the polynomial $Q(x)$, since $Q(x)$ satisfies the conditions). Notice that $Q$ must be a polynomial with rational coefficients (comes from finite differences), therefore there is an integer $c$ such that $cQ$ is a polynomial with integer coefficients. For some very large $x>n$, we find that \[\text{lcm}{}(x,x-1,\dots{},x-k)\geq{}\frac{x(x-1)\dots{}(x-k)}{ck!(k-1)!\dots{}1!}\]and by bounding on $q_x$ (Since by the second condition, we must have that $|q_x|<P(x)$), we find that we must have $Q(x)=q_x$ for all $x$, and we are done.

The hardest part of the problem is really getting started. Fix $\deg Q = d = \deg P$, and let $Q$ be the polynomial with degree $d$ that agrees with $q_i$ for $0 \leq i \leq d$. We can assume that $Q$ is an integer polynomial; otherwise just transform $Q \to kQ$ where $kQ \in \mathbb Z[X]$ and show that $kQ(n) = kq_n$ for every $n$. Now, for any $n \geq d$, note that $$q_n \equiv Q(n) \pmod {\operatorname{lcm}(n, n-1, \dots, n-d)}.$$Call this $A_n$. Claim. $A_n = O(n^{d+1})$. Proof. Intuitively, this is because for large $n$, the numbers ``don't share many common factors." More rigorously, $$A_n > \frac{n(n-1)\dots(n-d)}{\prod_{i<j} \gcd(i, j)} = O(n^{d+1}). \ \blacksquare$$ To finish, pick very large $n$ and suppose that $q_n \neq Q(n)$; then it follows that $|q_n - Q(n)| > A_n$. But by the claim this implies $|q_n| > P(n)$, contradiction! Thus, $q_n$ and $Q(n)$ agree at infinitely many values, and $Q(n) = q_n$ for all $n$.

Let $N$ be a sufficiently large integer and let $Q$ be the interpolation polynomial of the points $(0, q_0), (1, q_1), \dots, (N, q_N)$. We'll show that $Q$ is the desired polynomial. We can assume that $Q$ is an integer polynomial; otherwise just transform $Q \to kQ$ where $kQ \in \mathbb Z[X]$ and show that $kQ(n) = kq_n$ for every $n$. We'll do it by induction. Base case is clear. For induction step, assume $Q(n) \neq q_n$ for some $n$. Since $q_n \equiv q_i = Q(i) \equiv Q(n) (n - i)$, so $\text{lcm}(1, 2, \dots, n-1) \mid q_n - Q(n)$. Therefore there exists $k$ such that $q_n = Q(n) + \text{lcm}(1, 2, \dots, n-1)k$. Now consider the following claim: Claim: $\text{lcm}(1, 2, \dots, n)$ grows faster than any polynomial. Proof. Assume not. Then there exists $k$ such that $n^k > \text{lcm}(1, 2, \dots n)$ for all sufficiently large integer $n$. But we have $\text{lcm}(1, 2, \dots, n) > \prod_{p \le n} p^{\log_p(n) - 1} = \prod_{p \le n} \frac{n}{p} = \frac{n^{\pi(n)}}{p_1p_2\cdots p_{\pi(n)}} > \frac{n^{k+1}}{p_1p_2\cdots p_{k+1}}$, hence we get $n^k > \frac{n^{k+1}}{p_1p_2\cdots p_{k+1}}$ for all sufficiently large $n$, a contradiction. $\blacksquare$ Note that $|Q(i)| < P(i)$ for all $0 \le i \le N$, so $\deg Q \le \deg P$. Thus $q_n$ has to be equal to $Q(n)$, otherwise we get $\text{lcm}(1, 2, \dots, n)$ is bounded by some polynomial, contradicting the claim. Hence the induction step is proved. $\blacksquare$ Remark. In fact, we have $\text{lcm}(1, 2, \dots, n) = n \cdot \text{lcm}(\binom{n-1}{0}, \binom{n-1}{1}, \dots, \binom{n-1}{n-1}) \ge \binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{n-1} = 2^{n-1}$, which immediately implies the claim.

The main idea of this problem is the following lemma: Lemma. For all non-negative integers $d$, we have \[\text{lcm}(n,n-1,\ldots,n-d)=O(n^{d+1})\]Proof. For the upper bound, simply note that \[\text{lcm}(n,n-1,\ldots,n-d)\leq n(n-1)\cdots(n-d)=O(n^{d+1}),\]while for the lower bound, we use the fact that for $1\leq i < j\leq d$, we have $\gcd(n-i, n-j)\leq j-i$, which means \[\text{lcm}(n,n-1,\ldots,n-d)\geq \frac{n(n-1)\cdots(n-d)}{\prod_{1\leq i < j\leq n}(j-i)}=O(n^{d+1}),\]so the lemma is true. $\blacksquare$ Let $d$ be the degree of $P$. So, $q_n=o(P(n))=o(n^d)$ for sufficiently large $n$. By Lagrange Interpolation, there exists a unique rational polynomial $R$ of degree at most $d$ such that $R(i)=q_i$ for each $0\leq i\leq d$. Claim: $R(n)=q_n$ for all sufficiently large $n$. Proof. Note that we have \[q_n\equiv q_i\equiv R(i)\equiv R(n)\pmod{n-i}\]for each $0\leq i\leq d$. Hence, we have \[q_n\equiv R(n)\pmod{\text{lcm}(n-1,n-2,\ldots,n-d)}\Longrightarrow q_n=k\ \text{lcm}(n-1,n-2,\ldots,n-d)+R(n)\]So, if $k\neq0$, then $q_n=O(n^{d+1})$. But we also have $q_n=o(n^d)$ for sufficiently large $n$. This means $O(n^{d+1})=o(n^d)$, which is absurd. Hence, $k=0$ is forced for large $n$, which means $q_n=R(n)$, as desired. $\blacksquare$ Finish: Note that for any $m$ and sufficiently large $n$, we have that \[q_m\equiv q_n\equiv R(n)\equiv R(m)\pmod{n-m}\]So, $n-m\mid q_m-R(m)$ for all sufficiently large $n$, which forces $q_m=R(m)$. So, $R$ is the required construction for $Q$. $\blacksquare$

First we clearly see that $P$ must have positive leading coefficient as it is positive for all $n$. Consider the polynomial constructed by Lagrange Interpolation with rational coefficients and degree the same as that of $P$ so that $i$ maps to $q_i$ for all $ i \in \{0, 1, \ldots, d\}$ and $N$ be a positive integer satisfying that this polynomial times $N$ has integer coefficients. Let $R(x)$ be this polynomial with integer coefficients. Additionally, let $x_i = N q_i$ for each $i$. It suffices to show there exists a polynomial $S$ with $S(n) = x_n$ for all $n$. Clearly $m - n \mid x_m - x_n$ for all $m,n$. WLOG that $R(x)$ has a nonnegative leading coefficient (since we can switch $x_i$ with $- x_i$ and all the conditions stay the same). We see that $R(i) = x_i \forall i\in \{0,1, \ldots,d\}$. Claim: For all sufficiently large positive integers $n$, we have $R(n) = x_n$. Proof: Suppose otherwise for some large $n$. We have $n - i \mid x_n - x_i$ for any $0 \le i \le d$, so $x_n \equiv R(i) \pmod{n-i}$. Hence $x_n \equiv R(n) \pmod{n-i}$, so\[x_n \equiv R(n) \pmod{\mathrm{lcm}(n-d, n-(d-1), \ldots, n)}\]Now, we see that\[\mathrm{lcm}(n-d, n-(d-1), \ldots, n) \ge \frac{\prod_{i=0}^d (n - (d - i)) }{\prod_{n-d \le i < j \le n}\gcd(i,j) } \ge \frac{\prod_{i=0}^d (n - (d - i)) }{\prod_{n-d \le i < j \le n} (j-i)} \ge \frac{\prod_{i=0}^d (n - (d - i)) }{d^{d^2}} \]The RHS is a polynomial with degree $d + 1$ and positive leading coefficient, so for sufficiently large $n$, it exceeds $N P(n) + R(n) + 1434$. Suppose that $x_n \ne R(n)$ for some sufficiently large $n$. Then $|x_n|$ is at least $|R(n) - \mathrm{lcm}(n-d,n-(d-1), \ldots, n)|$. As $n$ is large, $\mathrm{lcm}(n-d, n-(d-1),\ldots, n)$ exceeds $N P(n) + R(n) + 1434$, so $|x_n| \ge N P(n) + 1434 > N P(n)$, which is a contradiction since $|x_n|= N |q_n| < N P(n)$. $\square$ Let $r$ be any positive integer and $m$ be any positive integer with $q_m = R(m)$. We have $m - r \mid R(m) - x_r$, however, we also have $m - r \mid R(m) - R(r)$, so\[ m - r \mid (R(m) - R(r)) - (R(m) - x_r) = x_r - R(r),\]so taking $m$ sufficiently large gives that $x_r = R(r)$, so we can just set $S(x) = R(x)$ (in particular $Q(x) = \frac{R(x)}{N} $ ).

Let $Q(x)$ be the polynomial such that $Q(0)=q_0$, $Q(1)=q_1$, \dots, $Q(d)=q_d$ where $d$ is the degree of $P(n)$, note that for all $n$ we have $q_n\equiv Q(n) \pmod{\text{lcm}(n(n-1)(n-2)\dots(n-d))}$, thus by taking large enough $n$ and using the fact that $\text{lcm}(n(n-1)(n-2)\dots(n-d))\geq \frac{n(n-1)(n-2)\dots(n-d)}{1!\cdot 2!\cdot 3!\dots d!}$ we get that for all large enough $n$ that $q_n=Q(n)$ and thus from the bound on small $n$ we can also get that for all $n$ $Q(n)=q_n$.