Finite certificates for differential recurrences
A polynomial sequence with a rational generating function satisfies a pure-lag recurrence, while interlacing criteria need a first-order differential recurrence. One polynomial identity links the two, so the differential recurrence follows from the lag recurrence and finitely many seeds.
Results
Let $K$ be a field and $P_0,P_1,\dotsc\in K[x]$. A pure-lag recurrence of order $k$ with coefficients $a_i\in K[x]$ is $$ P_{n+k}=\sum_{i<k}a_i\,P_{n+i}, $$ and a lift with $d_1,d_0,A_1,A_0,B\in K[x]$ is $$ d(n)\,P_{n+1}=A(n)\,P_n+B\,P_n',\qquad d(n)=nd_1+d_0,\quad A(n)=nA_1+A_0 . $$ Let $S$ be the forward shift on sequences, and put $$ R_n=P_{n+k}-\sum_{i<k}a_iP_{n+i},\qquad L_n=d(n)P_{n+1}-A(n)P_n-BP_n', $$ the lag defect and the lift defect, and $\chi(S)=S^k-\sum_ia_iS^i$.
Theorem (defect identity). For every sequence $P$, with no recurrence assumed, $$ (\chi(S)L)_n=d(n+k)\,R_{n+1}-A(n+k)\,R_n-B\,R_n'+(J(S)P)_n, $$ where $$ J(S)=\sum_{i<k}\Bigl((k-i)\,a_id_1\,S^{i+1}-\bigl((k-i)\,a_iA_1+B\,a_i'\bigr)S^i\Bigr). $$
Corollary (propagation). Suppose $J=\gamma\,\chi$ for some $\gamma\in K[x]$.
- If $R_n=0$ for all $n$ and $L_n=0$ for $n<k$, then $L_n=0$ for all $n$.
- If $L_n=0$ for all $n$, $d(n+k)\ne0$ for all $n$, and $R_0=0$, then $R_n=0$ for all $n$.
- If $L_n=0$ for all $n$ and $d(n)=\delta_n\in K\setminus\{0\}$, then $P_{n+1}=\delta_n^{-1}\bigl(B\,P_n'+A(n)\,P_n\bigr)$.
Theorem (filtered finite check). Let $N$ multiply the $n$-th entry of a sequence by $n$, let $D$ differentiate every entry, and let $F=\sum c_{u,j,s}\,N^uS^jD^s$ be a finite combination with coefficients in $K[x]$ of weight below $h$, meaning $u+s<h$ for every word. Let $p$ be a monic polynomial of degree $k$ in $S$ with coefficients in $K[x]$, and let $f$ satisfy $p(S)f=0$. Then $p(S)^hFf=0$, and $$ Ff=0\iff (Ff)_n=0\ \text{ for all } n<hk . $$ Underlying this, if $p(S)^qf=0$ then $p(S)^{q+1}Df=0$.
Use
To prove interlacing for a sequence given by a pure-lag recurrence, it suffices to check $J=\gamma\chi$, finitely many seeds and $d(n+k)\ne0$. The derivative recurrence of the corollary then feeds the root-window theorems. See also the Sturm sequence families.
References
Finite verification of recurrences on symmetricfunctions.com.