Generalized Fibonacci analogue of the coefficient-statistics rationality conjecture

The conjecture holds for every $k\ge2$, every factor width $h\ge1$, every complex polynomial $P$, arbitrary complex factor coefficients, and every nonzero weak composition of mixed-moment exponents.

Write

$$Q_n(X) = P(X)\prod_{i=1}^n \left(1+\sum_{j=1}^h a_jX^{F_{i+j-1}^{(k)}}\right) = \sum_{p\ge0}c_n(p)X^p.$$

For a nonzero weak composition

$$\alpha=(\alpha_0,\ldots,\alpha_{s-1}),$$

we prove that

$$V(n)=\sum_{p\ge0}\prod_{j=0}^{s-1}c_n(p+j)^{\alpha_j}$$

has a rational generating function.

Let $A$ be the integer companion matrix of

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

Its unique expanding root $\beta\in(1,2)$ is Pisot. Indeed,

$$(T-1)q_k(T)=T^{k+1}-2T^k+1.$$

For $r>1$ sufficiently close to $1$,

$$r^{k+1}+1<2r^k,$$

so Rouché's theorem gives exactly $k$ roots of $(T-1)q_k(T)$ inside $|T|=r$. One is $1$, and the sole outside root is $\beta$. There are no other unit-circle roots, since $|T|=1$ and $|2-T|=1$ force $T=1$. Therefore

$$\mathbb R^k=E_u\oplus E_s, \qquad \dim E_u=1, \qquad A|_{E_u}=\beta, \qquad \rho(A|_{E_s})<1.$$

We first establish a finite-carry principle. Fix any finite alphabet $U\subset\mathbb Z^k$, and evolve integer carries by

$$q_0=0, \qquad q_{i+1}=Aq_i+u_i.$$

Accept when $L(q_n)=c$, where $L(q)=q_1$ and $c\in\mathbb Z$ is fixed. Choosing a contracting norm on $E_s$, every reachable state satisfies

$$\|\pi_s q_i\| \le \frac{\max_{u\in U}\|\pi_su\|}{1-\theta}, \qquad 0<\theta<1.$$

Normalize the expanding eigenvector as

$$v=(1,\beta,\ldots,\beta^{k-1}),$$

so $L(v)=1$. Writing $\pi_uq=x(q)v$, the acceptance condition and the stable bound uniformly bound $x(q_n)$. If $q$ can be extended by $r$ letters to an accepting state, projection onto $E_u$ gives

$$|x(q)| \le B_f+ \frac{\max_{u\in U}|x(u)|}{\beta-1},$$

independently of $r$. Thus every reachable and co-reachable carry lies in a fixed bounded subset of the integer lattice, which contains only finitely many states. The same reasoning works simultaneously for any fixed number of carry coordinates. A finite weighted adjacency matrix $M$ therefore gives

$$\sum_{n\ge0}e^{\mathsf T}M^nb\,z^n = e^{\mathsf T}(I-zM)^{-1}b \in\mathbb C(z).$$

Now put

$$R=\sum_j\alpha_j>0$$

and expand the mixed moment into $R$ labeled representation rows, assigning exactly $\alpha_j$ rows offset $j$. Write

$$P(X)=\sum_{e\in E}p_eX^e, \qquad w_j=(F_j,\ldots,F_{j+k-1})^{\mathsf T}, \qquad Aw_j=w_{j+1}.$$

For each row $v$, select $e_v\in E$ and factor letters

$$\ell_{i,v}\in\{0,1,\ldots,h\},$$

with $w_0=0$ and $a_0=1$. Its represented exponent is

$$T_v=e_v+ L\left(\sum_{i=1}^nA^{i-1}w_{\ell_{i,v}}\right).$$

The mixed-moment condition is

$$T_v=p+r_v$$

for fixed row offsets $r_v$. Eliminating $p$ gives, for every $v\ge2$,

$$L(q_v)=(r_v-r_1)-(e_v-e_1),$$

where, scanning factor positions in reverse order, the carry evolves by

$$q_v\longmapsto Aq_v+w_{\ell_v}-w_{\ell_1}.$$

This is exactly the finite-carry situation above, with finite synchronized alphabet

$$(\ell_1,\ldots,\ell_R)\in\{0,1,\ldots,h\}^R$$

and complex transition weight $\prod_va_{\ell_v}$. Summing over the finitely many choices of $P$-monomials preserves rationality.

If a row of offset zero exists, the common base index $p$ is automatically nonnegative. Otherwise choose the smallest occurring offset

$$j_0=\min\{j:\alpha_j>0\}.$$

The unconstrained automaton also counts only the finitely many extraneous base indices

$$-j_0\le p<0.$$

For each fixed exponent $b$, the coefficient $c_n(b)$ is eventually constant because $F_i\to\infty$. Therefore the total contribution from these finitely many negative $p$ is eventually constant in $n$, and its generating function is rational. Subtracting it proves

$$\boxed{\sum_{n\ge0}V(n)z^n\in\mathbb C(z).}$$

The case $P=0$ is immediate. The all-zero composition is excluded only because its defining expression would be the divergent sum $\sum_{p\ge0}1$.