Conjecture on recurrence orders and coefficient polynomials for power sums

The exact-order assertion is false, although the affine-coefficient assertion is true.

Take $k=9$, and write $S_n=(s^9)_n$. The defining transfer system yields, for every admissible $q\ge5$ and every $n\ge7$,

$$\begin{aligned} S_n={}&(q+62)S_{n-1}+(447q+1288)S_{n-2} +(2433q-15116)S_{n-3}\\ &+(10555-2431q)S_{n-4} +(3662-450q)S_{n-5}-450S_{n-6}. \end{aligned}$$

These are exactly the six coefficients printed in the source's $k=9$ row; its purported seventh coefficient is explicitly $c_7(q)=0$. Thus the recurrence has order at most six, although the conjecture predicts

$$\left\lfloor\frac92\right\rfloor+3=7.$$

Moreover, six is the exact minimal order. At $q=5$, the first eleven values are

$$2,\ 514,\ 39880,\ 4470930,\ 438529598,\ 45014063550,\ 4547625234042,\ 461974238315026,\ 46840025812751018,\ 4752325523662690738,\ 482052722208599420434.$$

Their Hankel determinant is

$$\det(S_{i+j+1})_{0\le i,j<6} =-2^{23}3^{22}5^97^7\cdot31\cdot71\ne0.$$

Any recurrence of order at most five would make this determinant vanish. Consequently the minimal order is exactly six, not seven.

A corrected general statement also follows directly from the source transfer matrix $M_k(q)$. If $C_j$ denotes its $j$-th column, then

$$C_j=C_{k-j}\quad(1\le j<k), \qquad 2C_{k+1}=\sum_{j=1}^{k-1}C_j.$$

Hence

$$\operatorname{rank}M_k(q)\le\left\lfloor\frac k2\right\rfloor+2,$$

and the homogeneous characteristic annihilator

$$(X-1)\det(XI-M_k(q))$$

gives an eventual recurrence of order at most $\lfloor k/2\rfloor+3$. Equality need not hold, as $k=9$ shows.

Finally, homogenizing the affine transfer recurrence gives the augmented matrix

$$A(q)=A(0)+q(e_k+e_{k+1}) (e_0^{\mathsf T}+e_k^{\mathsf T}-2e_{k+2}^{\mathsf T}).$$

The $q$-dependent perturbation has rank one, so determinant multilinearity makes $\det(XI-A(q))$ affine in $q$. The same holds after removing its initial powers of $X$. Thus all resulting characteristic recurrence coefficients have degree at most one in $q$, proving the conjecture's second assertion while disproving its first.