Denominator-shape conjecture for generalized Fibonacci coefficient moments

There is an important transcription correction: the latest primary source, Conjecture 5.6 of arXiv:2101.02131v3, permits coefficients aᵢ(t,u) with u=t^{k−1}. The problem page omits this indispensable second argument. Ekhad and Zeilberger, arXiv:2103.12855, had already identified the correction and verified bounded cases. The following proves the corrected source conjecture for every moment order r≥2 and every generalized Fibonacci order k≥2, including its final odd-index assertion.

Write z for the generating-function variable, q=zᵏ, u=t^{k−1}, and m=r−1. For 1≤s,j≤m define

W_{sj}(t)=1_{j≥s} binom(r−s,j−s)t^{j−s} +1_{j≤s} binom(s,j)t^{r−s+j},

U=diag(u,u²,…,u^m), c_s=binom(r,s)t^s, b_s=u^s t^{r−s}.

Set

N(q)=det(I−qUW),

D(q,z)=[1−(1+tʳ)z]N(q)−zq cᵀ adj(I−qUW)b.

Then the exact universal formula is

Jᵣ⁽ᵏ⁾(t,z)=N(zᵏ)/D(zᵏ,z).

In particular m=r−1 works for every k; the numerator has only powers z^{jk}, while the denominator has precisely the permitted powers z and z^{jk},z^{jk+1}, with coefficient polynomials in t and u independent of k.

Here is a direct proof. The primary source's proved free-word Lemma 5.2 yields an equal-weight two-row parser with states 0,±1,…,±k. Writing ε∈{−1,1}, its allowed difference transitions are

0 —0→ 0, 0 —ε→ ε, εj —ε→ ε(j+1) (1≤j<k), εk —0→ ε, εk —(−ε)→ 0.

Run r−1 such parsers, comparing each row to the first, and weight an r-bit column by t^{number of ones}. The useful states are exactly the all-zero state O and states whose nonzero coordinates all equal one common signed stage εj. Indeed, restricting to any two parsers leaves only (0,0),(s,0),(0,s),(s,s) on accepting paths: unequal positive stages, unequal negative stages, and opposite stages lie in a forward-invariant rejecting set. Conversely, every stated common-stage state opens, advances, and closes. There are exactly 1+k(2ʳ−2) useful states.

Quotient by row permutations, writing A_{s,j} when the high group has s rows and stage j. From O, the self-loop has weight 1+tʳ and the transition to A_{s,1} has weight c_s. Interior transitions A_{s,j}→A_{s,j+1} have weight t^s. At stage k, closing has weight t^{r−s}, and the total weight of transitions to A_{j,1} is W_{sj}(t), obtained by choosing the changing rows in the old high or low group.

Let O(z) and G_s(z) be accepted-continuation series at O and A_{s,1}. These exact transitions give

O=1+z[(1+tʳ)O+cᵀG],

G_s=zᵏt^{s(k−1)}[t^{r−s}O+∑{j=1}^m W{sj}(t)G_j].

Hence (I−qUW)G=qbO. Substitution and the adjugate identity prove O=N/D, and O is exactly the rth coefficient-moment generating function.

The final formal coefficient does not vanish: W(t)=I+O(t), so det(UW)=u^{r(r−1)/2}(1+O(t)). In the coefficient of zq^{r−1}, the adjugate contribution is u^{r(r−1)/2}O(t²), whereas the other contribution has leading term (−1)ʳu^{r(r−1)/2}. Substitution u=t^{k−1} preserves nonvanishing for every k≥2.

It remains to prove the source's delicate specialized odd-index statement. Put t=u=1, c_s=binom(r,s), and write 𝟙=(1,…,1)ᵀ. Then

D=N−zL, L(q)=2N(q)+q cᵀadj(I−qW)𝟙.

The matrix W is self-adjoint for C=diag(binom(r,1),…,binom(r,r−1)), since

binom(r,i)binom(r−i,j−i)=binom(r,j)binom(j,i).

An explicit solution of Wx=𝟙 is

x_j=(−1)^{j+1}/2 if r is even,

x_j=[(−1)^{j+1}(r−j)+1_{j=1}+1_{j=r−1}]/(2r) if r is odd.

Direct binomial summation gives cᵀx=1 when r is even and cᵀx=3/2 when r is odd. Self-adjointness and 𝟙=Wx imply that c annihilates ker W. Therefore

L(q)/N(q)=2−cᵀx+cᵀ(I−qW)^{-1}x → 1 if r is even, 1/2 if r is odd,

as q→∞. In particular deg L=deg N, even when W is singular. Thus the largest specialized nonzero denominator index is 2deg(N)+1, which is odd. This proves every clause of the corrected primary-source conjecture uniformly for all r,k≥2.