Explicit parity-count generating function conjecture for generalized Fibonacci products

Fix $k\ge2$, set $a_i=F^{(k)}_{i+k-1}$, and let $h_k(n)$ count the odd coefficients of

$$\prod_{i=1}^n(1+x^{a_i}).$$

We prove

$$\sum_{n\ge0}h_k(n)z^n =\frac{1+2z^k}{1-2z+2z^k-2z^{k+1}}$$

uniformly for every $k\ge2$.

Read binary words from the lowest-index weight to the highest. The recurrence for the weights gives the weight-preserving rewrite

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

Every weight class therefore has a representative avoiding $1^k0$. By the free-monoid decomposition in Lemma 5.2, every nontrivial equal-weight pair generator has one row containing $1^k0$. Thus two avoiding representatives cannot differ, proving that each weight class has exactly one canonical representative.

Fix such a representative $b$. The same free decomposition identifies all words of its weight with tilings of $b$ by singleton letters and blocks

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

where each star is an arbitrary binary letter. Consequently its coefficient is odd precisely when its number of these tilings is odd.

Over $\mathbb F_2$, let $b_0$ count completed tilings and $b_1,\ldots,b_k$ count the stages of unfinished blocks. The initial vector is $(1,0,\ldots,0)$. Reading a zero or one gives

$$\begin{array}{c|ccc} &b_0'&b_1'&b_{j+1}'\ (1\le j<k)\\ \hline 0&b_0&b_0+b_k&b_j\\ 1&b_0+b_k&b_k&0 \end{array}$$

and a zero after $k$ consecutive ones is forbidden. A state accepts exactly when $b_0=1$.

Encode the binary state vector by $v=\sum_{j=0}^kb_j2^j$ and retain the capped trailing-one count. All useful reachable states belong to the families

$$\begin{aligned} P_j&=(2^{j+1}-1,0)&& (0\le j\le k),\\ R_j&=(1,j)&&(1\le j\le k),\\ Q_j&=\left(1+\sum_{i=j+1}^k2^i,0\right)&&(1\le j<k),\\ B&=(2,1),\\ C_j&=(2^j,0)&&(1\le j\le k),\\ D&=(3,1). \end{aligned}$$

Here $P,R,Q,D$ accept and $B,C$ do not. Direct substitution gives the complete transition graph

$$\begin{array}{c|cc} \text{state}&0&1\\ \hline P_j,\ j<k&P_{j+1}&R_1\\ P_k&Q_1&B\\ Q_j,\ j<k-1&Q_{j+1}&B\\ Q_{k-1}&P_0&B\\ R_j,\ j<k&P_1&R_{j+1}\\ R_k&\text{forbidden}&R_k\\ B&C_2&\text{dead}\\ C_j,\ j<k&C_{j+1}&\text{dead}\\ C_k&C_1&D\\ D&P_2&R_2 \end{array}$$

for every $k\ge2$.

Write each state also for the generating function of its accepted continuations, and set $q=z^k$, $R=R_1$, $Q=Q_1$. Summing the finite chains gives

$$\begin{aligned} R&=\frac{1+zP_1(1-q/z)}{1-z},\\ P_0&=\frac{(1+zR)(1-q)}{1-z}+qP_k,\\ P_1&=\frac{(1+zR)(1-q/z)}{1-z}+\frac qzP_k,\\ Q&=\frac{(1+zB)(1-q/z)}{1-z}+\frac qzP_0,\\ P_k&=1+z(Q+B),\\ B&=\frac{qD}{1-q},\\ D&=(1-z)(P_1+R)-1. \end{aligned}$$

These formal-power-series equations have a unique solution. With

$$\Delta=1-2z+2q-2zq,$$

direct substitution gives

$$P_0=\frac{1+2q}{\Delta}, \qquad P_1=\frac1{(1-q)\Delta}, \qquad R=\frac{1-2q^2}{(1-q)\Delta},$$ $$P_k=\frac{1+2q-2z}{(1-z)\Delta}, \qquad B=\frac{q}{(1-q)\Delta}, \qquad D=\frac1{\Delta}, \qquad Q=\frac{P_k-1}{z}-B.$$

The initial state is $P_0$. Substituting $q=z^k$ proves the conjectured generating function for every $k\ge2$.