Explicit formula conjecture for the third coefficient moment

About 5 years old · traced to 2021

Fix $k\geq 2$ and let $v_3^{(k)}(n,t)$ be the sum of the cubes of the coefficients of

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

Define

J_3^{(k)}(t,x)=\sum_{n\geq 0}v_3^{(k)}(n,t)x^n.

Third-moment generating-function conjecture. One has

J_3^{(k)}(t,x)=\frac{1-t^3(1+t^3)^2x^k+t^9(t^3-1)^2x^{2k}}{D_3^{(k)}(t,x)},

where

D_3^{(k)}(t,x)=1-(1+t^3)x-t^3(1+t^3)^2x^k+t^3(1+t^9)x^{k+1}+t^9(t^3-1)^2x^{2k}-t^9(t^3-1)^2(t^3+1)x^{2k+1}.

This conjecture gives an explicit rational form for the third coefficient moment in the generalized Fibonacci setting. The surrounding discussion says that the free generators needed for higher moments are difficult to determine, and gives no evidence of resolution.

References

Primary source

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

coefficient-moments generalized-fibonacci-numbers generating-functions

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

The formula was previously checked only in finitely many cases, but a posted argument now claims a proof for every allowed $k$ ; that proof has not been independently verified.

The conjecture gives a rational generating function for the third coefficient moment in the generalized Fibonacci setting. Stanley’s 2021 paper records it as Conjecture 5.4, attributed to Doron Zeilberger, and presents a corrected version.

Known results

Zeilberger verified the corrected formula computationally for $k\leq 5$ (2021).
Stanley’s paper states the higher-moment generator structure is difficult and leaves the formula conjectural for general $k\geq 2$ .

Posted attempt

A posted argument claims a complete proof for every $k\geq 2$ , using a free equal-weight-pair decomposition, a finite pair automaton, permutation-symmetric states, and a linear generating-function system. It also claims to recover the corrected sign and formula, but the argument has not been independently verified.

Current status (as of August 2026): The formula is verified for $k\leq 5$ , while a complete proof for all $k\geq 2$ is claimed in an unverified posted argument.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

Ekhad and Zeilberger previously identified the sign error in the original conjecture and stated the corrected formula, verifying it for $k\le5$ ; see arXiv:2103.12855, page 16. The contribution here is a proof of their corrected formula for every $k\ge2$ .

Put

u=t^{k-1}, \qquad J_3^{(k)}(t,z) = \sum_{n\ge0}v_3^{(k)}(n,t)z^n.

Define

N_k(t,z) = 1-u(u+1)(t^3+1)z^k + u^3(t^3-1)^2z^{2k},

and

\begin{aligned} D_k(t,z) ={}&1-(t^3+1)z-u(u+1)(t^3+1)z^k\\ &+u(u+1)(t^6-t^3+1)z^{k+1}\\ &+u^3(t^3-1)^2z^{2k}\\ &-u^3(t^3-1)(t^6-1)z^{2k+1}. \end{aligned}

Then, for every $k\ge2$ ,

\boxed{ J_3^{(k)}(t,z)=\frac{N_k(t,z)}{D_k(t,z)}. }

The final denominator term has a minus sign, as in the correction of Ekhad and Zeilberger.

To prove this uniformly, use the free equal-weight-pair decomposition from Lemma 5.2. The resulting deterministic pair automaton has states

0,\ \pm1,\ \ldots,\ \pm k,

with initial and accepting state $0$ . For a column difference $d$ , its transitions are

0\xrightarrow{0}0, \qquad 0\xrightarrow{\varepsilon}\varepsilon,

\varepsilon j\xrightarrow{\varepsilon} \varepsilon(j+1)\quad(1\le j<k),

\varepsilon k\xrightarrow{0}\varepsilon, \qquad \varepsilon k\xrightarrow{-\varepsilon}0,

where $\varepsilon\in\{1,-1\}$ .

A third coefficient moment counts ordered triples of equal-weight binary words. Run two copies of this automaton on the column differences

d_2=b_2-b_1, \qquad d_3=b_3-b_1,

and give each triple column weight $t^{b_1+b_2+b_3}$ . The useful synchronized states are exactly

O=(0,0), \qquad (j,j),\ (j,0),\ (0,j) \quad(1\le|j|\le k).

Every other reachable state belongs to the forward-invariant nonaccepting set

\{(i,j):1\le i,j\le k,\ i\ne j\} \cup \{(-i,-j):1\le i,j\le k,\ i\ne j\} \cup\{(1,-1),(-1,1)\},

and may be discarded.

Permutation symmetry of the three words combines the six useful states at each stage into two orbits

U_j=\{(j,j),(-j,0),(0,-j)\},

V_j=\{(-j,-j),(j,0),(0,j)\}.

Their weighted transitions are

\begin{array}{c|c|c} \text{state}&\text{target}&\text{weight}\\ \hline O&O&1+t^3\\ O&U_1&3t^2\\ O&V_1&3t\\ U_j&U_{j+1}&t^2\quad(j<k)\\ V_j&V_{j+1}&t\quad(j<k)\\ U_k&U_1&1+t^3\\ U_k&V_1&2t^2\\ U_k&O&t\\ V_k&V_1&1+t^3\\ V_k&U_1&2t\\ V_k&O&t^2. \end{array}

Write $O,U,V$ for the accepted-continuation generating functions from $O,U_1,V_1$ , and put $q=z^k$ . Summing the stage chains gives

\begin{aligned} O&=1+z\big((1+t^3)O+3tV+3t^2U\big),\\ U&=qu^2\big((1+t^3)U+tO+2t^2V\big),\\ V&=qu\big((1+t^3)V+2tU+t^2O\big). \end{aligned}

Solving this linear system yields

O= \frac{1-u(u+1)(t^3+1)q+u^3(t^3-1)^2q^2} {1-(t^3+1)z-u(u+1)(t^3+1)q +u(u+1)(t^6-t^3+1)qz +u^3(t^3-1)^2q^2 -u^3(t^3-1)(t^6-1)q^2z}.

Substituting $q=z^k$ proves the corrected conjecture in full.

For comparison with the original misprinted formula, $k=2,t=2,n=5$ gives the actual third moment $101817$ , whereas its erroneous positive final sign predicts $94761$ . The correction of that sign is due to Ekhad and Zeilberger; the uniform proof above extends their finite verification to all $k$ .