Rationality conjecture for factor-occurrence generating functions in k-Bonacci words

Complete proof for factors of arbitrary length, with an explicit denominator exponent and recurrence onset.

Let $k\ge2$, and let $W_n=\phi_k^n(0)$ be the finite infinite-alphabet $k$-Bonacci words from Ghareghani, Golafshan, Mohammad-Noori, and Sharifani, arXiv:2604.01488. For any nonempty finite word $B$ over $\mathbb N$, including words that do not occur, define

$$c_B(n)=|W_n|_B,\qquad C_B(y)=\sum_{n\ge0}c_B(n)y^n,\qquad D_k(y)=1-y-y^2-\cdots-y^{k-1}.$$

Occurrences are counted with overlap. Write

$$m=\min(B),\qquad M=\max(B),\qquad q=\left\lfloor\frac{m}{k}\right\rfloor.$$

We prove the stronger explicit statement

$$\boxed{D_k(y)^{q+1}C_B(y)\in\mathbb Z[y].} \tag{1}$$

The paper's previously established Lemmas 1 and 3 supply the decomposition

$$W_n=W_{n-1}W_{n-2}\cdots W_{n-k+1} \bigl(k\oplus W_{n-k}\bigr),\qquad n\ge k, \tag{2}$$

and state that the final letter of $W_j$ is $j$. Here $k\oplus V$ adds $k$ to each letter of $V$.

Suppose $n\ge M+k$. Every boundary between consecutive blocks in (2) is immediately preceded by the final letter of some unshifted block $W_j$, where

$$n-k+1\le j\le n-1.$$

Consequently that boundary is immediately preceded by a letter

$$j\ge n-k+1\ge M+1>M.$$

Any occurrence crossing such a boundary would contain that letter, which is impossible because every letter of $B$ is at most $M$. This argument works for words of arbitrary length, including occurrences that would cross several boundaries.

Hence every occurrence lies wholly inside exactly one block of (2). The unshifted blocks give $c_B(n-1),\ldots,c_B(n-k+1)$. The shifted final block contributes zero if $m<k$; otherwise its occurrences correspond bijectively to occurrences of $B-k$ in $W_{n-k}$. Thus

$$c_B(n)=\sum_{r=1}^{k-1}c_B(n-r) +\boldsymbol 1_{\{m\ge k\}}c_{B-k}(n-k), \qquad n\ge M+k. \tag{3}$$

Set

$$Q_B(y)=D_k(y)C_B(y) -\boldsymbol 1_{\{\min(B)\ge k\}}y^kC_{B-k}(y).$$

By (3), all coefficients of degree at least $M+k$ vanish. Therefore

$$Q_B(y)\in\mathbb Z[y],\qquad \deg Q_B\le M+k-1. \tag{4}$$

Iterating along $B,B-k,\ldots,B-qk$, the last of which has minimum less than $k$, gives

$$C_B(y)= \sum_{r=0}^{q} \frac{y^{kr}Q_{B-rk}(y)}{D_k(y)^{r+1}}.$$

It follows that

$$D_k(y)^{q+1}C_B(y) = \sum_{r=0}^{q} y^{kr}Q_{B-rk}(y)D_k(y)^{q-r} \in\mathbb Z[y],$$

proving (1). Moreover,

$$\deg\!\left(D_k(y)^{q+1}C_B(y)\right) \le M+k-1+q(k-1).$$

Consequently the occurrence counts satisfy a homogeneous linear recurrence with characteristic polynomial dividing

$$\bigl(x^{k-1}-x^{k-2}-\cdots-x-1\bigr)^{q+1}$$

at every index $n\ge M+k+q(k-1)$.

For the exact stated conjecture $k\ge3$, an admissible uniform exponent is therefore

$$s(B)=1+\left\lfloor\frac{\min(B)}k\right\rfloor.$$

The proof also covers $k=2$, arbitrary factor lengths, nonfactors, overlapping occurrences, and an explicit finite numerator construction. The block decomposition and the length-one and length-two cases were already established in the cited paper; the disappearing-boundary argument proves the previously open arbitrary-length assertion.