Solving homogeneous linear congruence recurrence relation with variable coefficients

Question

For a homogeneous linear recurrence congruence relation with constant coefficients, the linear algebra method is well known (see here). Given a homogeneous linear recurrence congruence relation $\sum_{i=0}^{d}[c_{i,0}+(n-i)c_{i,1}]a_{n-i} \equiv 0 \pmod{p}$ with prime $p$ and known coefficients $c_{\cdot, \cdot}$, I'd like to ask how to compute large terms using some kind of linear algebra method?

Answer 1

Note that you require $c_{0,1}\equiv 0$ and $c_{0,0}\not\equiv 0$ to solve for $a_n$ in terms of $a_{n-1},a_{n-2},\dots,a_{n-d}$ for all $n$.

If you really want such "linear algebra method": Note that the recurrence is the same after shift by $p$, so you can just do $\mathbf{x}_n=(a_{np+p-1},a_{np+p-2},\dots,a_{np})$, $\mathbf{x}_{n+1}=C^{(p)}\mathbf{x}_n$, $C^{(p)}=C_{p-1}C_{p-2}C_{p-3}\dots C_0$ and recover a constant-coefficient recurrence (assuming $p\geq d$, otherwise you need to use $kp$ where $kp\geq d$). Of course this traded recurrence of larger order, so if $p\gg d$ this is impractical.