Rationality conjecture for generalized Fibonacci coefficient congruence counts

The generating function is rational for every order $k\ge2$, every modulus $m\ge1$, and every residue class, including zero.

Set

$$w_i=F^{(k)}_{i+k-1}, \qquad I_n(X)=\prod_{i=1}^n(1+X^{w_i}) =\sum_{s=0}^{d_n}c_n(s)X^s, \qquad d_n=\sum_{i=1}^nw_i.$$

The recurrence $w_{i+k}=w_i+\cdots+w_{i+k-1}$ gives the weight-preserving rewrite

$$1^k0\longrightarrow0^k1.$$

Every represented exponent therefore has a binary representative avoiding $1^k0$. By the free equal-weight-pair decomposition in Lemma 5.2, every nonsingleton pair generator has one row containing $1^k0$. Hence two avoiding representatives cannot differ: each represented exponent has exactly one canonical word.

Fix its canonical word $b$. The same free decomposition shows that $c_n(s)$ equals the number of factorizations of $b$ into singleton letters and blocks

$$0^k(*0^{k-1})^j1, \qquad j\ge0,$$

where each star is an arbitrary binary letter. This equality holds over the integers.

For $m\ge2$, count these tilings modulo $m$ with a state vector

$$(v_0,v_1,\ldots,v_k) \in(\mathbb Z/m\mathbb Z)^{k+1},$$

initially $(1,0,\ldots,0)$. Here $v_0$ counts completed tilings and the other coordinates track the $k$ unfinished-block stages. The letter transitions are

$$\begin{array}{c|ccc} \text{letter}&v_0'&v_1'&v_{j+1}'\ (1\le j<k)\\ \hline 0&v_0&v_0+v_k&v_j\\ 1&v_0+v_k&v_k&0. \end{array}$$

Also retain the trailing run of ones, capped at $k$, and forbid a zero after a run of length $k$. This finite automaton accepts precisely the canonical words, and its final coordinate $v_0$ is the corresponding coefficient modulo $m$. It has at most

$$(k+1)m^{k+1}$$

states.

Let $M$ be its finite integer adjacency matrix, $e$ the initial-state vector, and $\mathbf1_a$ the vector selecting final states with $v_0=a$. The number $C_a(n)$ of represented exponents with coefficient congruent to $a$ satisfies

$$C_a(n)=e^{\mathsf T}M^n\mathbf1_a,$$

and therefore

$$\sum_{n\ge0}C_a(n)z^n =e^{\mathsf T}(I-zM)^{-1}\mathbf1_a \in\mathbb Q(z).$$

For $a\ne0$, every coefficient in the specified residue class corresponds to a represented exponent, so

$$h_{m,a}^{(k)}(n)=C_a(n).$$

For $a=0$, internal zero coefficients must also be counted. They are incorporated exactly by

$$h_{m,0}^{(k)}(n) =d_n+1-\sum_{a=1}^{m-1}C_a(n).$$

Since $w_n$ satisfies the order-$k$ generalized Fibonacci recurrence, its partial sum $d_n$ has a rational generating function, with characteristic polynomial dividing

$$(T-1)(T^k-T^{k-1}-\cdots-T-1).$$

Thus the zero-residue generating function is rational as well. For $m=1$, every coefficient belongs to the zero class, so $h_{1,0}^{(k)}(n)=d_n+1$ directly.

Therefore all conjectured residue-count generating functions are rational for every $k,m,a$.