Explicit formula conjecture for the third coefficient moment

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.

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

Explicit formula conjecture for the third coefficient moment

Progress summary

Primary source

Solutions 1