It suffices to show that when $\deg P \ge 2,$ it cannot possibly be true that $\{a_i\}$ contains an element of $\mathbb{N} / \{1\}^b$ ($b$th powers of stuff $>1$) for all $b \in \mathbb{N}$. Suppose that $P$ is some integer polynomial of degree $\ge 2.$ Assume, for contradiction, that for all $b \in \mathbb{N}$, $\{a_i\}$ contains some element of $\mathbb{N}/\{1\}^b.$ Clearly, this implies that $\{a_i\}$ is unbounded, and so $|a_i|$ eventually increases strictly. Let $b_i = a_{i+1} - a_i$ for $i \ge 0.$ Then, it's well-known that $x-y | P(x) - P(y), \forall x, y \in \mathbb{Z}$, and so therefore we have that $b_i | b_{i+1} \forall i \in \mathbb{Z}_{\ge 0}.$ Notice that if $p$ is a prime and $k \in\mathbb{N}$ such that $p^k | b_i$, then we must have that $a_i \equiv 0, 1$ (mod $p^k$). This is because we'd otherwise have that $a_t$ is always $a_i$ (mod $p^k$) for $t \ge i$, which is never a $p^{k-1}(p-1)$th power by Euler's Theorem, which would clearly produce a contradiction by picking $b = p^{k-1}(p-1)v$ for large enough $v \in \mathbb{N}$ (so as to ensure that $a_j$ for $j < i$ isn't a $b$th power). Therefore, we know that $b_i | a_i(a_i-1), \forall i \in \mathbb{Z}_{\ge 0}.$ This alone is enough to imply that $P$ must be quadratic, since otherwise large enough $|a_i|$ would ensure that $|b_i| = |P(a_i) - a_i|$ would exceed $|a_i(a_i-1)|$. In view of this, let $P(x) = ax^2 + bx + c,$ for some $a, b,c, \in \mathbb{Z}$ with $a$ nonzero. Observe that if $c$ is nonzero then we have for large $i$ that $\gcd(b_i, a_i) \le c$, which together with $b_i | a_i(a_i -1)$ gives that $b_i | c(a_i-1),$ clearly a contradiction by taking large $i$ with $|c(a_i-1)| < |b_i| = |P(a_i) - a_i|.$ Therefore, we have that $P(x) = ax^2 + bx = x(ax+b).$ If $|a| > 1$, then $b_i | a_i(a_i-1) \Leftrightarrow (aa_i^2 + (b-1)a_i) | (a_i^2 - a_i)$ easily gives a contradiction for $i$ big enough so that $|aa_i^2 + (b-1)a_i| > |a_i^2 - a_i|.$ We therefore have that $a = \pm 1.$ If $a = -1$, then clearly $a_i$ will be negative for sufficiently large $i$, which easily gives a contradiction (just take $b$ so that $2^b$ exceeds all the positive $a_i$'s). Finally, when $P(x) = x^2+bx$, we obtain a contradiction simply by taking $b = 2l$ for sufficiently large $l$, since there are only finitely many $x \in \mathbb{Z}$ where $x^2 + bx$ is a perfect square. As we've obtained a contradiction in all cases, our initial assumption that $\{a_i\}$ contained an element of $\mathbb{N} / \{1\}^b$ for all $b \in \mathbb{N}$ cannot hold, as desired. $\square$

Solved with Th3Numb3rThr33. Observe that for each \(b\), the sequence contains infinitely many powers of \(b\). (We can find powers of \(b\), \(2b\), \(3b\), and so on.) Claim: For all \(i\), \[a_{i+1}-a_i\quad\text{divides}\quad a_i(a_i-1).\] Proof. Observe that \(a_{i+1}-a_i\mid a_{j+1}-a_j\) for all \(j\ge i\), so \[a_i\equiv a_{i+1}\equiv a_{i+2}\equiv\cdots\pmod{a_{i+1}-a_i}.\]But there are infinitely many \(b\)th powers in the sequence, so for any choice of \(b\) and \(i\), \(a_i\) is a \(b\)th power residue modulo \(a_{i+1}-a_i\). Now for each \(p^e\parallel a_{i+1}-a_i\), let \(b=\varphi(p^e)\), so \(a_i\equiv 0,1\pmod{p^e}\). The claim follows from Chinese Remainder theorem. \(\blacksquare\) Claim: \(\deg P\le2\). Proof. Follows from \(|a_{i+1}-a_i|\le|a_i(a_i-1)|\). \(\blacksquare\) It will suffice to show no quadratic \(P\) work. Let \(P(x)=cx^2+dx+e\). Claim: \(P(x)\) is of the form \(\pm x^2+dx\); that is, \(e=0\) and \(c=\pm1\). Proof. We use Claim 1 again: Check that \(\gcd(a_i,a_{i+1}-a_i)=\gcd(a_i,P(a_i))=\gcd(a_i,e)\mid e\), so Claim 1 may be strengthened to \[a_{i+1}-a_i\quad\text{divides}\quad e(a_i-1).\]By degree counting, this is absurd unless \(e=0\). Henceforth \(P(x)=x(cx+d)\). Now, \(a_{i+1}-a_i=a_i(ca_i+d-1)\) divides \(a_i(a_i-1)\), so \[ca_i+d-1\quad\text{divides}\quad a_i-1.\]It follows from \(|ca_i+d-1|\le|a_i-1|\) that \(c=\pm1\). \(\blacksquare\) The remaining cases may be verified by hand: If \(c=-1\), then the sequence \(a_1\), \(a_2\), \(\ldots\) is eventually negative and therefore a square finitely often. If \(c=1\) and \(d\ne0\), then \(4P(x)=4\left(x^2+dx\right)=(2x+d)^2-d^2\) is a square finitely often, so the sequence \(a_1\), \(a_2\), \(\ldots\) contains finitely many squares. Finally, \(P(x)=x^2\) obviously fails. For instance, take \(b\) an odd integer such that \(x\) is not a perfect \(b\)th power.

Notice that the sequence $\{a_n\}$ is not bounded above, and $P$ has positive leading coefficient. Meanwhile, for each $b$ there exists infinitely many $b^{th}$ power in the sequence. Now suppose $P$ is not linear. Claim 1. $P$ cannot be monic. Proof. Otherwise let $$P=\sum_{i=0}^ka_ix^i$$where $a_k=1$, let $m=\lfloor \frac{a_{k-1}}{k}\rfloor$, then for sufficiently integer $x$ we have $$(x+m-1)^k< P(x)<(x+m+1)^k$$hence we must have $P(x)=(x+m)^k$ for infinitely many $x$, which implies $P(x)\equiv (x+m)^k$. If $k\geq 2$, then for sufficiently large $x$, $P(x)$ is a $k^{th}$ power, and so $P(x)+m$ is not a $k^{th}$ power, and $(P(x)+m)^k$ is not a $(k^2)^{th}$ power. Hence there are only finitely many $(k^2)^{th}$ power, contradiction. $\blacksquare$ Now we consider the case where $P$ is not monic. Then notice that for sufficiently large $x$ we have $P(x)-x>x^2$. Pick sufficiently large $m$ and let $$C=P(a_m)-a_m$$Suppose $C=p_1^{\alpha_1}...p_{c}^{\alpha_c}$, we denote $a_m$ by $x$. Claim 2. There exists $1\leq i\leq c$ such that $x\not\equiv 0,1\pmod{p_i^{\alpha_i}}$ Proof. Otherwise, WLOG assume $p_1^{\alpha_1},...,p_j^{\alpha_j}|x$ and $p_{j+1}^{\alpha_{j+1}},...,p_c^{\alpha_c}|x-1$, then $$x\geq \max\{p_1^{\alpha_1}p_2^{\alpha_2}...p_j^{\alpha_j},p_{j+1}^{\alpha_{j+1}}...p_c^{\alpha_c}\}>\sqrt{p_1^{\alpha_1}...p_j^{\alpha_j}(p_{j+1}^{\alpha_{j+1}}. ..p_c^{\alpha_c}+1)}>\sqrt{C}$$contradiction. $\blacksquare$ Now we have $a_{m+1}=P(a_m)\equiv a_m \pmod{p_i^{\alpha_i}}$, hence for each $N\geq m$ we have $a_N\equiv a_m\pmod{p_i^{\alpha_i}}$. However, by Euler-Fermat Theorem, for each $r\in\mathbb Z$ we have $$r^{\alpha_i\varphi{p_i^{\alpha_i}}}\equiv 0,1\pmod{p_i^{\alpha_i}}$$Since $a_m\not\equiv 0,1\pmod{p_i^{\alpha_i}}$, the terms in the sequence after $a_m$ are all not a $(\alpha_i\varphi{p_i^{\alpha_i}})^{th}$ power, contradiction. This completes the proof.

TheUltimate123 wrote: Claim: For all \(i\), \[a_{i+1}-a_i\quad\text{divides}\quad a_i(a_i-1).\] Proof. Observe that \(a_{i+1}-a_i\mid a_{j+1}-a_j\) for all \(j\ge i\), so \[a_i\equiv a_{i+1}\equiv a_{i+2}\equiv\cdots\pmod{a_{i+1}-a_i}.\]But there are infinitely many \(b\)th powers in the sequence, so for any choice of \(b\) and \(i\), \(a_i\) is a \(b\)th power residue modulo \(a_{i+1}-a_i\). Now for each \(p^e\parallel a_{i+1}-a_i\), let \(b=\varphi(p^e)\), so \(a_i\equiv 0,1\pmod{p^e}\). The claim follows from Chinese Remainder theorem. \(\blacksquare\) Here's another way to finish after the Claim. We assume contrary $\deg P \ge 2$. Clearly all $a_i$'s are distinct, otherwise sequence is eventually periodic and hence bounded, contradiction. So $|a_k|$ is large for all large $k$. But then $$ 2|a_{k+1} - a_k| = 2 |P(a_k) - a_k| \ge |a_k(a_k - 1)| > 0 $$for all large $k$. Hence $P(a_k) - a_k \in \{a_k(a_k - 1),-a_k(a_k - 1)\}$ for all large $k$. Hence $P(x) \equiv x^2$ or $P(x) \equiv -x^2 + 2x$. It is easy to see $P(x) \equiv x^2$ doesn't work. Assume $P(x) \equiv -x^2 + 2x = -x(x-2)$. Note all $a_i$'s cannot be power of $2$. Pick a $a_k$ and an odd prime $q \mid a_k$. Observe the sequence $$ \nu_q(a_k),\nu_q(a_{k+1}),\nu_q(a_{k+2}), \ldots $$is constant, say all terms equal $\lambda \ ge 1$. But then for any $b > \lambda$, the sequence $a_k,a_{k+1},\ldots$ cannot contain a $b$-th power, contradiction. $\blacksquare$

Note that we have $a_{n} - a_{n-1} | a_{n+1} - a_n | a_{n+2} - a_{n+1}$ and so on, this implies that all of $a_{n-1}, a_n, \cdots$ are the same modulo $a_n - a_{n-1}$. Since the sequence must be unbounded (else we can't have big enough powers of integers), we can get the value $a_n - a_{n-1}$ to be as large as needed. Say $r \equiv a_k$ for all $k \geqslant n-1$ is the one that is a $b$th power for any value of $b$ (if a $z$th power is already over, take a $2z$th power for instance), this means that we must have that $r \equiv 0$ or $1 \pmod {a_n - a_{n-1}}$, in particular, this means that $a_{n} - a_{n-1} | a_{n-1}(a_{n-1} - 1)$. This, taking $a_{n-1} = x$, implies that $P(x) - x | x(x-1)$ for infinitely many values of $x$. But if the polynomial $P$ has degree $d$, then the LHS has degree $d$ while the RHS has degree $2$, which gives a size contradiction unless $d = 2$ (if its linear we're done). Further, this polynomial must be such that $P(x) - x = \pm x(x-1)$ by size as the coefficients of the polynomial are integers. But if $P(x) = x^2$, it cannot contain an odd power beyond what $a_0 = n$ contains, so it fails. If $P(x) = -x^2 - 2x$, note that $P(x) = -(x+1)^2 + 1$, and so is a square finitely often, implying that the sequence cannot have arbitrarily large $2k$th powers for big enough $k$, again a contradiction, so we're done.

Nice Problem. Claim 1: $deg(P) \leq 2$

Claim 2: $P(x)$ is of form $x^2+bx$

Now if $d \neq 0$ then $4P(x) = (2x+d)^2-d^2$ which can only be perfect square finitely many times contradiction. and obviously $P(x)=x^2$ fails and hence $P$ is linear

Assume $deg(P) \ge 2$ for all $j \in \mathbb{Z^+}$ we have that $a_{k+1}-a_k|a_{k+j}-a_{k+j-1}$ so all values of $a_{k+j}(mod a_{k+1}-a_k)$ is same. then choose one of the perfect $\phi(a_{k+1}-a_k).m$-th power to show \(a_{k+j}\equiv 0,1\pmod{a_{k+1}-a_k}\) so $a_{k+1}-a_k|a_{k+1}.(a_{k+1}-1)$ so $a_{k+1}-a_k|a_k^2-a_k$ so $P(a_k) \leq a_k^2$ so rest of the question is $P(x)=x^2-ax+b$. now we shouldn't squeeze it into two square so $P(x)=(x-n)^2$ but now from $a_{k+1}-a_k|a_k^2-a_k$ we get easy contradaction.