Rationality conjecture for generalized Fibonacci coefficient congruence counts

About 5 years old · traced to 2021

Fix $k\geq 2$ , $m\geq 1$ , and $0\leq a<m$ . Set

I_n^{(k)}(x)=\prod_{i=1}^n\left(1+x^{F_{i+k-1}^{(k)}}\right).

Let $h_{m,a}^{(k)}(n)$ be the number of coefficients of $I_n^{(k)}(x)$ congruent to $a$ modulo $m$ , and define

H_{m,a}^{(k)}(x)=\sum_{n\geq 0}h_{m,a}^{(k)}(n)x^n.

Congruence-count rationality conjecture. The generating function $H_{m,a}^{(k)}(x)$ is rational.

This extends the corresponding rationality theorem in the ordinary Fibonacci case to generalized Fibonacci numbers. The source gives no proof or resolution.

References

Primary source

Richard P. Stanley, “Theorems and Conjectures on Some Rational Generating Functions”, arXiv:2101.02131 (2021).

generalized-fibonacci-numbers generating-functions modular-arithmetic

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written argument claims a complete proof in every order and modulus, but no independent verification has been found, so the generalized conjecture is not settled.

Stanley’s 2021 work proves the ordinary Fibonacci case and records the generalized statement, for order $k\geq 2$ , as a conjecture. The claim concerns rationality of the generating function counting coefficients in each residue class modulo $m$ .

Known results

Ordinary Fibonacci case: rationality proved in Stanley (2021); the generalized case was left conjectural.

Posted attempt

A reader-written argument claims a complete proof for every $k\geq 2$ , $m\geq 1$ , and residue $a$ , using canonical binary representatives, a finite automaton, and a matrix generating-function argument; it has not been independently verified.

Current status (as of August 2026): The ordinary Fibonacci case is settled, while the generalized conjecture has an unverified complete-proof claim and no independent confirmation.

Sources

arxiv.org

ProofThis solution needs a summarySee full solutionHide full solution

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$ .