Let $f_i(x)$ be polynomials with integer coefficients.
Define the integer linear recurrence with polynomial coefficients:
$$ a(n)=f_1(n) a(n-1)+f_2(n)a(n-2)+\cdots +f_d(n) a(n-d) $$
and the initial terms $a(1),a(2)..., a(d)$ are given.
Let $p$ be prime and define $R(p)$ as the smallest integer such that $a(R(p)) \ne a(2 R(p))$ and $a(R(p)) \equiv a(2R(p)) \pmod{p}$.
Q1 How small can $R(p)$ be for all $p$, can we get $o(p)$ (small Oh on purpose)?
Q2 Can we get bound $O(\sqrt{p})$ possibly related to the birthday paradox?
If we define $a(n)=n a(n-1)$ then $a(n)=n!$ which has period one and super-exponential growth, but the pre-period is $p-1$, not answering the question.
For $d=2$ and $f_i$ constant we believe the answer is known to be negative.
In case of positive solution, it might be tractable with brute force search, but we didn't waste enough electricity.
