In the first step, we show that all $a_i$ must be of the form $\frac{k_i}{n}$ where $k_i\in \mathbb{Z}$ and $n$ is a fixed natural dependent only on $P$ and $a_1$. First, we write the polynomial $P$ as $\frac{Q}{N}$ where $Q=\sum_{i=0}^d b_ix^i$ is an integer polynomial, $N$ is the lcm of the denominators of all coefficients and $d$ is the degree of $P$. Claim 1. For any prime $p$ and $i\in \mathbb{N}$, we have \[\nu_p(a_i)\ge \min(-\nu_p(b_d), \nu_p(a_1))\]Proof: Suppose $\nu_p(a_i)<-\nu_p(b_d)$. Now, \[\nu(b_da_i^d)=\nu(b_d)+d\nu_p(a_i)<j\nu_p(a_i) \text{ for any $j<d$ as $\nu_p(a_i)<0,-\nu_p(b_d)$}.\]Thus, $\nu_p(b_da_i^d)<\nu_p(b_ja_i^j)$ for all other $j$. Thus, $\nu_p(b_da_i^d)=\nu_pQ(a_i)\implies \nu_p(P(a_i))=\nu_p(Q(a_i))-\nu_p(N)<\nu_p(a_i) <0$ since $d\ge 2$. Since $\nu_p(i) \geq 0$, $$\nu_p(a_{i-1})=\nu_p(P(a_i)-i) = \nu_p(P(a_i)) < \nu_p(a_i).$$Repeating this, we get that \[\nu_p(a_1)<\nu_p(a_2)<\cdots \nu_p(a_i)\]Thus, if $\nu_p(a_i)<-\nu_p(b_d)$ then $\nu_p(a_i)>\nu_p(a_1)$ implying the claim! Lemma 1. There exists an $N$ such that for all $i\in \mathbb{N}$, we have that $N\cdot a_i$ is integral. Proof: Follows directly from Claim $1$. Claim 2. The sequence $a_i$ is unbounded. Proof: If $a_i$ are bounded then $P(a_i)$ are also bounded (since $P$ is a continuous function). Thus $P(a_i)-a_{i-1}=i$ is bounded which is ridiculous. Thus, $a_i$ are unbounded.

We will first show that $P$ can have degree at most $2$ by a counting argument. Claim A1. There exists $m\in \mathbb{N}$ such that $\forall i> m$, $|a_i|<i$. Proof: Let $n_1$ be a number such that for all $x$ with $|x|>n_1$, we have $|P(x)|>2|x|$. Now, consider the minimal $j\ge 1$, such we have that $|a_j|> \max(j, n_1, |a_0|)$, then observe that: \[|a_{j-1}|\ge |P(a_j)|-j> 2|a_j|-j>|a_j|\]This contradicts the minimality of $j$. Thus, there is no such $j$. But since the sequence is unbounded, we must have that for all large $j$ such that \[\max(n_1, |a_0|)<j \hspace{0.5cm} \implies \hspace{0.5cm} |a_j|<j.\] Claim A2. (Few distinct $a_i$) There exists some $\alpha>0$ such that $|\{a_1, a_2, \ldots, a_n\}|<\alpha n^{\frac1d}$ for all $n\in \mathbb{N}$. Proof: From the previous claim, we get that there exists a $c>0$ such that $|a_n|<cn$ for all $n$. Now, we have that \[\{a_0, a_1, \ldots , a_n\}\subset [-cn, cn]\implies \{P(a_1)-1, P(a_2)-2, \ldots , P(a_{n+1})-n-1\}\subset [-cn, cn]\]Thus, $\{P(a_1), P(a_2), \ldots P(a_n)\}\subset [-(c+2)n, (c+2)n]$ for all large enough $n$. Now, there exists a $c'>0$ such that for all $n>0$, we have that for any $r$ with $|r|>c'n^{\frac1d}$, \[|P(r)|>(c+2)n\]Thus, \[\{a_1, a_2, \ldots, a_n\}\subset [-c'n^{\frac1d}, c'n^{\frac1d}]\]but then since $Na_i$ is integral for all $i$, we get that $|\{a_1, a_2, \ldots, a_n\}|< 4Nc'n^{\frac1d}$ where $4Nc'$ is a constant. So we just use $\alpha$ to denote this constant. Thus, we have \[|\{a_1, a_2, \ldots, a_n\}|<\alpha n^{\frac1d}.\] Claim A3. There exists a $\beta>0$ such that for all large $n$, we have that some value $b$ (which may depend on $n$) appears atleast $\beta n^{1-\frac{1}{d}}$ times in $a_1, a_2, \ldots, a_n$. Proof: This follows simply by pigeon hole principle on Claim A2. Lemma A1. For any $i\ne j$ with $i,j \ge 1$, we have that $a_i=a_j\implies a_{i-1}\ne a_{j-1}$. Proof: \[a_i=a_j\implies P(a_i)=P(a_j)\implies P(a_i)-i\ne P(a_j)-j\implies a_{i-1}\ne a_{j-1}.\] Due to Claim $A3$, we may suppose $a_{x_1}=a_{x_2}=\cdots =a_{x_{m}}$ where $1 \le x_i\le n$ for all $i$, and $m = \beta n^{1-\frac{1}{d}}$. Then by Lemma $A1$, all of $a_{x_1-1}, a_{x_2-1},\ldots, a_{x_{m}-1}$ are all pairwise distinct. Thus, for all large enough $n$, we have \[\beta n^{1-\frac{1}{d}}\le|\{a_{x_1-1}, a_{x_2-1},\ldots, a_{x_{m}-1}\}|\le |\{a_0,\ldots, a_n\}|\le \alpha n^{\frac 1d} + 1 \le 2 \alpha n^{\frac 1d}.\] Thus, for all large enough $n$, we have $n^{1-\frac2d}\le 2 \alpha\beta^{-1}$. This is a contradiction if $d>2$! Observe that the same proof gives us a contradiction if $|\{a_1, \ldots ,a_n\}|=o(\sqrt{n})$ even when $d=2$. Thus, we can assume that there exists a $\gamma>0$ such that for infinitely many $n$, $|a_n|>\sqrt{\gamma n}$. Now, we handle $d=2$ separately. By completing the square, we assume that our polynomial is of the form $P(x)=c(x-a)^2+b$ for some $a, b, c\in \mathbb{R}$ and $c\ne 0$. We can assume the $N$ from Lemma 1 also satisfies $Na \in \mathbb{Z}$ by increasing it if necessary. Thus, \[P(x)-P(y)=c(x-y)(x+y-2a)\] If $M>|P(x)-P(y)|>0$, then $0<|x-y|\cdot |x+y-2a|<\frac{M}{|c|}$. Thus, both are non zero. If we also know that $xN$, $yN$ and $aN$ are integral then we get that $|Nx-Ny|\cdot |Nx+Ny-2Na|<\frac{MN^2}{|c|}$. Now, since both elements are atleast $1$, we get that there exists a $\delta >0$ such that $|x|, |y|<\delta$. Corollary. For any integer $M$, there exists a constant $\delta_M>0$ such that if $a_{n_1}=a_{n_2}$ and $0<|n_1-n_2| \leq M$ then $\max(|a_{n_1+1}|, |a_{n_2+1}|)<\delta_M$. Now, consider some $n$ large enough such that $|a_{n+2}|>\sqrt{\gamma n}$. \begin{align*} a_{n+2}-a_{n+1}& =P(a_{n+3})-P(a_{n+2})-1\\ a_{n+1}-a_{n}& =P(a_{n+2})-P(a_{n+1})-1\\ a_{n}-a_{n-1}& =P(a_{n+1})-P(a_{n})-1\\ \end{align*} Thus, we have \[P(a_{n+3})-P(a_{n+2})=c(a_{n+3}-a_{n+2})(a_{n+3}+a_{n+2}-2a).\] Observe that at least one of $|a_{n+3}-a_{n+2}|$ and $|a_{n+2}+a_{n+3}-2a|$ is $\geq \sqrt{\gamma n}-|a|$ as their sum is $\ge 2\sqrt{\gamma n}-2|a|$. This in fact holds for any $a_i,a_j$ as long as one of them is big. Also, observe that either the terms are $0$ or both at least $\frac{1}{N}$. Thus, there exists a $\varepsilon>0$ such that for all large $n$, we have that $|a_{n+2}-a_{n+1}|>\sqrt{\varepsilon n}$ if $a_{n+2}>\sqrt{\gamma n}$ (we can take any $\varepsilon<\frac{c^2 \gamma}{N^2}$) unless $a_{n+3}=a_{n+2}$ or $a_{n+3}+a_{n+2}=2a$ (again, this holds for any $a_i,a_j$ as long as one of them is big). The first case would be a contradiction since then we would need \[\sqrt{\gamma n}<|a_{n+2}|=|a_{n+3}|<\delta_1\]but we have picked a sufficiently large $n$ so that this does not happen. Thus, $a_{n+2}\ne a_{n+3}$. All in all, either $|a_{n+2}-a_{n+1}|>\sqrt{\varepsilon n}$ or $a_{n+2}+a_{n+3}=2a$. Recall from proof of Claim A2 that $|a_i|=O(\sqrt n)$ for $i \leq n+5$. Thus for any $i \leq n+4$, if $|a_i-a_{i-1}|>\sqrt{\varepsilon n}$, then $$|a_i+a_{i-1}-2a|<\frac{|a_{i-1}-a_{i-2}|+1}{|c| \sqrt{\varepsilon n}} = O(1).$$Thus either $|a_{n+2}+a_{n+1}-2a|=O(1)$, which would imply $|a_{n+1}|>\sqrt{\gamma n}-O(1)$, or $a_{n+3}+a_{n+2}=2a$, which implies $P(a_{n+2})=P(a_{n+3})$, so $a_{n+1}=a_{n+2}+1$, so $|a_{n+1}|>\sqrt{\gamma n}-O(1)$ in any case. Thus $|a_{n+1}|$ is also large, so we can repeat the above arguments. Since "largeness" can be cascaded down, we can also assume $|a_{n+3}|,|a_{n+4}|, |a_{n+5}|$ are large, by shifting the indices if needed (there won't be any issues as long as we shift by $O(1)$ indices). Again we get either $|a_{n+1}+a_n-2a|=O(1)$, or $a_{n+1}+a_{n+2}=2a$ and $a_n=a_{n+1}+1$. Also $|a_n|>\sqrt{\gamma n}-O(1)$. However, if $a_{n+2}+a_{n+3}=2a$, then $a_{n+1}=a_{n+2}+1$, so then we can't have $a_{n+1}+a_{n+2}=2a$, so $|a_{n+1}+a_n-2a|=O(1)$, and $2a-a_{n+3}+1=a_{n+2}+1=a_{n+1}$. This means $|a_{n+3}-a_n|=O(1)$, which implies $|P(a_{n+4})-P(a_{n+1})|=O(1)$. If $P(a_{n+4}) \neq P(a_{n+1})$, we get a contradiction since $|a_{n+1}|$ is big. Thus equality must hold, so $a_{n+4}=a_{n+1}$ (impossible since $|a_{n+2}|>\delta_3$ is large), or $a_{n+4}+a_{n+1}=2a$, so $a_{n+4}=a_{n+3}-1$, so $a_{n+5}=2a-a_{n+4}=a_{n+1}$ which is impossible since $|a_{n+2}|>\delta_4$ is large. Therefore $a_i+a_{i+1} \neq 2a$ for any $i$ in the $|a_i|$ large range. So $|a_i+a_{i+1}-2a|=O(1)$ always (i.e., $a_i$ "flips" around $a$ every time), which implies $|a_{n+2}-a_n|=O(1)$ and $|a_{n+3}-a_{n+1}|=O(1)$ by using triangle inequality on two consective such bounds. Thus $|P(a_{n+3})-P(a_{n+1})|=O(1)$. Similar to the above analysis, we must have $P(a_{n+3})=P(a_{n+1})$, and $a_{n+3}=a_{n+1}$ is impossible since $|a_{n+2}|>\delta_2$, so we must have $a_{n+3}+a_{n+1}=2a$, which contradicts $|a_{n+3}-a_{n+1}|=O(1)$. This gives us our final contradiction, and we are done.

First, we consider the case that $d$ is odd. Then, $\exists M, c>0$, such that if $|x|>M$ and $y$ is some real then if $|a_{i+1}|\ge 2M, |a_i|, |a_{i-1}|, |a_{i-2}|, \ldots, |a_1|$, we get \[\frac{|P(x)-P(y)|}{|x-y|}\ge c(|x|)^{d-1}.\]Thus, \[c(a_{i+1}^{d-1})|a_{i+1}-a_i|\le|P(a_{i+1}-P(a_i))|\le |a_{i}-a_{i-1}|+1 \leq 2|a_{i+1}|+1\] Thus, \[|a_{i+1}-a_i|\le \frac{2}{a_{i+1}^{d-2}}+\frac{1}{a_{i+1}^{d-2}}\]but as $|a_{i+1}|$ becomes very large, this forces $a_{i+1}=a_i$ since we know that either $|a_{k}-a_l|=0$ or $|a_k-a_l|>\frac{1}{n}$ since all $a_i$ are of the form $\frac{k_i}{n}$. Thus, $a_{i+1}=a_i$ and $a_i$ satisfies the same conditions, thus, $a_i=a_{i-1}$. Thus, $P(a_i)=a_i+i$ and $P(a_{i})=a_i+i-1$ which is a contradiction! Now, if $d\ge 4$ is even. Observe that there exists $M, c>0$ such that if $|x|>M$ then $|P(x)-P(x-\frac{1}{n})|\ge cx^{d-1}$. Now, let $\alpha$ be such that $P(x)-P(\alpha-x)=R(x)$ is of degree at most $d-2$. There is a unique such $\alpha$ as the coefficient of $x^{d-1}$ in $R(x,y)=P(x)-P(y-x)$ is linear in $y$. Now, there is also a $M', c'>0$ such that if $x\ne y, |x|>M$, then \[|P(x)-P(y)|\ge c' \min(|x-y|, |x+y-\alpha|) \cdot x^{d-1}\] Thus, if we have $|a_{i+1}|\ge 10^{100}M'n^{100}, |a_i|-M', |a_{i-1}|-2M', |a_{i-2}|-3M'$. \[\min(|(a_{i+1}-a_i)|,|(a_{i+1}+a_i-\alpha)|)\cdot |a_{i+1}|^{d-1}|\le |P(a_{i+1})-P(a_i)|\le |a_i-a_{i-1}|+1\] Thus, \[ \min(|a_{i+1}-a_i|, |a_{i+1}+a_i-\alpha|)\le \frac{|a_{i}-a_{i-1}|}{|a_{i+1}^{d-1}|}+\frac{1}{a_{i+1}^{d-1}} \]But then this gets arbitrarily small as $|a_{i+1}|$ gets larger and larger. Again since $a_i$ are of the form $\frac{k_i}{n}$, the LHS is bounded below unless it's $0$. Thus, eventually, for all large terms, we have $a_{i+1}-a_i=0$ or $a_{i+1}+a_{i}=\alpha$. But then the sequence is not unbounded which is a contradiction! Now, finally we consider $d=2$. First, we get that $\min (|a_{i+1}-a_i|, |a_{i+1}+a_i-\alpha|)$ is bounded by some constant $\beta$. Now, if $|a_i-a_{i-1}|<\beta$ and $|a_{i+1}|$ is large then we get that either $a_{i+1}=a_i$ or $a_{i+1}+a_i=\alpha$. But repeating this in the case that $a_{i+1}=a_i$, tells us $a_{i+2}=a_{i+1}$ which is a contradiction as before. Thus, if $|a_i-a_{i-1}|<\beta$, then $a_{i+1}+a_i=\alpha$. Now, observe that $R(x)$ is a constant as it is of degree at most $2$. So, we have that $P(\alpha-x)+R=P(x)$ where $R$ is a constant. We have $|P(a_{i+1})-P(a_i)|=|a_{i+1}-a_i+1|$ if $a_{i+1}+a_{i}=\alpha$ but then $P(a_{i+1})-P(a_i)=R$. Thus, $|\alpha+1-2a_i|=|a_{i+1}-a_i+1|=R$. Thus, $a_i$ is bounded. Thus, if $a_i$ is large then $a_{i+1}+a_i\ne \alpha$. Thus, $|a_{i+1}-a_i|$ cannot be $<\beta$ if $a_i$ is large. Thus, we always have $|a_{i+1}+a_i-\alpha|<\beta$ for all large enough $i$. Thus, let $\beta_i=\alpha-a_{i+1}-a_i$. Now, \[-2a_{i}+1-\beta_i+\alpha=a_{i+1}-a_i+1=P(a_{i+1})-P(a_i)=P(\alpha-a_{i+1})-P(a_i)+R\]\[=P(a_i+\beta_i)-P(a_i)+R=P'(a_i)b_i+\frac{P''(a_i)}{2}b_i^2\] This fixes $b_i$ as the coefficient of $a_i$ gets fixed. Thus, $a_i+a_{i+1}$ is fixed when $a_i$ is large. That means $a_i=a_{i+2}$ and thus not unbounded. This is a contradiction! Thus, we are done!

Proceeding by contradiction, let $a_1, a_2, \dots$ be such a sequence, and $P = c_dx^d + \dots + c_0$ such a polynomial. Claim: There exists a positive integer $N$ such that $Na_i \in \mathbb{Z}$ for all $i$. Proof: Fix an arbitrary prime $p$. We first show that $\nu_p(a_i)$ cannot achieve arbitrarily small values. Suppose this were the case. Let $M$ be any positive integer, and fix a large enough $i$ with \[\nu_p(a_i) \leq \nu_p(a_j)\]for all $1 \leq j \leq i$ (thus a ``prefix'' min) and $\nu_p(a_i) \leq -M$. For such an $i$, we then find that $\nu_p(P(a_i))$ is equal to $\nu_p(c_d a_i^d)$ since eventually the $\nu_p$ of this is smaller than the other individual summands $\nu_p(c_k a_i^k)$ for $k < d$. Thus we have \[\nu_p(P(a_i)) \leq d \nu_p(a_i) + O(1)\]At the same time, $a_{i-1}+i$ has $\nu_p$ at least as large as $\min(\nu_p(a_{i-1}), 0)$, which is larger than $\nu_p(a_i)$ in either case. So we have \[d \nu_p(a_i)+O(1) \geq \nu_p(a_i)\]which becomes impossible due to $d \geq 2$ and $\nu_p(a_i) \leq -M$ for $M$ large enough. We next show that for each large enough prime $p$, we have $\nu_p(a_i) \geq 0$ throughout. For $p$ large enough, we have $\nu_p(c_i) = 0 = \nu_p(a_0)$ for all $0 \leq i \leq d$. Now if $i \geq 1$ is minimal with $\nu_p(a_i) < 0$, then we see that $\nu_p(P(a_i)) < 0$ as well. Since $P(a_i) = a_{i-1}+i$ and $\nu_p(i) \geq 0$, this implies $\nu_p(a_{i-1}) < 0$, contradicting $i$'s minimality. Thus we can look out for these ``small'' primes, and since the $\nu_p(a_i)$ for each of these is bounded, we can find an appropriate $N$ so that $Na_i \in \mathbb{Z}$ for all $i \geq 1$. $\square$ Claim: $|a_i| = O(i^{1/d})$ for $i \geq 1$. Proof: We assume that we are trying to show $|a_i| \leq Ci^{1/d}$ for some absolute positive constant $C$, and accordingly pick some large enough one in the end. WLOG choose $C$ large enough so that it holds for $i = 1$, and now pick the first contradictory $j > 1$. Then, \[|a_j| > Cj^{1/d} > C(j-1)^{1/d} \geq |a_{j-1}|\]. Thus \[|P(a_j)| = |a_{j-1}+j| \leq |a_{j-1}| + |j| \leq |a_j|+j\]and we have $j \geq |P(a_j)|-|a_j|$. We now see that owing to $|P(a_j)| = \Omega(a_j^d)$, we have a contradiction to this by choosing $C$ large enough, and so the claim holds good. $\square$ Claim: $d = 2$. Proof: Suppose $d > 2$. Fix some $M$ and look at $Na_1, Na_2, \dots, Na_M$, where $N$ is the same integer as from the first claim. Each of these integers has absolute value at most $CNM^{1/d}$ for some $M$. Thus the first $M$ of the $a_i$ take $O(M^{1/d})$ distinct values. Look at pairs $(a_i, a_{i+1})$ for $1 \leq i < M$ now. There are up to $O(M^{2/d}) = o(M)$ of these, and since there are $M$ such pairs, some two pairs coincide, say $\{a_i, a_{i+1}\} = \{a_j, a_{j+1}\}$ for $i \ne j$. But now \[j+1 = P(a_{j+1})-a_j = P(a_{i+1})-a_i = i+1,\]a contradiction. Thus we must have $d = 2$. $\square$ Rename the sequence $a_i$ to $m_i$, and let the quadratic polynomial in question be $P(x) = a(x-b)^2+c$. We have \[a(m_i-b)^2+c = m_{i-1}+i\]Replacing $m_i$ with $m_i-b$, and $c$ with $c-b$, we obtain a recursion of the form \[am_i^2+c = m_{i-1}+i\]Here it is worth noting that $m_i$ still satisfy the first claim and the second claim, since we only translated the values by a fixed rational, $b$. We have $am_i^2 = (i-c)+m_{i-1}$ and the right side is nonnegative for large $i$ due to $m_i = O\left(i^{1/2}\right)$. Thus $a > 0$. Take $i$ large and we have \[|m_i| = \frac{\sqrt{i-c}}{\sqrt{a}} \left(1 + \frac{m_{i-1}}{i-c}\right)^{1/2} = \frac{\sqrt{i-c}}{\sqrt{a}} \left(1 + \frac{m_{i-1}}{2(i-c)} + O\left(\frac{m^2_{i-1}}{i^2}\right)\right)\]Owing to $m_i = O\left(i^{1/2}\right)$ we may simplify the above to \[|m_i| = \sqrt{\frac{i-c}{a}} + \frac{m_{i-1}}{2\sqrt{a(i-c)}} + O\left(i^{-1/2}\right)\]We can actually further simplify the above a bit more by replacing $i-c$ with $i$ (it can be seen that all the differences incurred by doing so are $O\left(i^{-1/2}\right)$). So \[|m_i| = \sqrt{\frac{i}{a}} + \frac{m_{i-1}}{2\sqrt{ai}}+o(1) \qquad (1)\]Since $m_{i-1}$ is $O\left(\sqrt{i}\right)$ the above tells us that $|m_i| = \sqrt{\frac{i}{a}} + O(1)$. Using this fact again, we obtain that \[\left| |m_i| - \sqrt{\frac{i}{a}}\right| = \frac{1}{2a}+o(1)\]Define $k_i = N|m_i|$ so that all the $k_i$ are positive integers, and moreover, \[\left|k_i - N\sqrt{\frac{i}{a}}\right| = \frac{N}{2a}+o(1)\]Comparing fractional parts of the above at $i = aM^2$ for $M$ large, we see that $2a \mid N$, say $N = 2at$ for a positive integer $t$. We further have \[|k_i - 2t\sqrt{ai}| = t + o(1)\]By comparing fractional parts, we find that $\{\sqrt{ai}\}$ is restricted to tinier and tinier intervals centered at the $k/2t$ for $0 \leq k \leq 2t$. When the $o(1)$ error goes below $\frac{1}{5t}$, small gaps in $[0, 1]$ will be created which $\{\sqrt{ai}\}$ can never hit, a contradiction due to Kronecker by selecting $i = m^2$ or $i = 2m^2$, depending on whether $a$ is not a perfect square or $2a$ is not a perfect square. This is the final nail in the coffin, and the problem is solved. $\blacksquare$