Supppose there are integers $a_1,a_2,\dots$ and a polynomial $p$ so that the integers $p(a_1),p(a_2)...$ satisfy some linear recurrence, i.e. $\sum p(a_i)x^i$ is a rational function of $x$. Must integers $b_i\in p^{-1}(p(a_i))$ so that $\sum b_ix^i$ is a rational function, necessarily exist?

(The answer is no if we ask for the function $\sum a_i x^i$ to be rational, as can be seen when $p(t)=t^2$ and $a_i$ being a random sequence of $\pm1$)