Fibonacci degree conjecture for Golombic and Levine polynomials

We prove both degree formulas simultaneously. Let

$$w=b_1^{m_1}\cdots b_k^{m_k},$$

and initially specialize every $m_h,b_h$ to a positive integer. For a positive word $u=(u_1,\ldots,u_L)$, define

$$\Gamma(u)=1^{u_1}2^{u_2}\cdots L^{u_L}, \qquad \mathcal L(u)=\operatorname{rev}(\Gamma(u)).$$

Choose either $\mathcal O=\Gamma$ or $\mathcal O=\mathcal L$, and write

$$u^{(t)}=\mathcal O^t(w),\qquad L_t=|u^{(t)}|.$$

Fix $t\ge1$, set $u=u^{(t)}$, and put

$$S=\sum_{i=1}^{L_t}u_i,\qquad T=\sum_{i=1}^{L_t}i u_i,\qquad M=\max_{1\le i\le L_t}u_i.$$

Both deployment and reversed deployment have the same length and sum of entries, so

$$S=L_{t+1},\qquad T=L_{t+2}.$$

Since all entries of the preceding row are positive, its deployment contains every label $1,\ldots,L_{t-1}$. Reversal preserves these labels, and therefore

$$M=L_{t-1}.$$

The upper bound $T\le L_tS$ is immediate. For the lower bound,

$$\begin{aligned} S^2 &=\sum_i u_i^2+2\sum_{i<j}u_iu_j\\ &\le M\sum_i u_i+2M\sum_j(j-1)u_j\\ &=M(2T-S)\le2MT. \end{aligned}$$

Consequently, both operators satisfy the universal inequalities

$$\boxed{\quad \frac{L_{t+1}^2}{2L_{t-1}} \le L_{t+2} \le L_tL_{t+1} \qquad(t\ge1). \quad} \tag{1}$$

Write $s_h=m_1+\cdots+m_h$, with $s_0=0$. Directly,

$$L_0=\sum_{h=1}^km_h,\qquad L_1=\sum_{h=1}^km_hb_h,$$

and

$$L_2 = \sum_{h=1}^kb_h \sum_{i=s_{h-1}+1}^{s_h}i = \frac12\sum_{h=1}^k b_hm_h(2s_{h-1}+m_h+1). \tag{2}$$

Fix all parameters except one $x$ at arbitrary positive integer values. If $x=m_j$, the initial degrees are

$$(d_0,d_1,d_2)=(1,1,2),$$

because the quadratic coefficient in $L_2$ is $b_j/2>0$. If $x=b_j$, the initial degrees are

$$(d_0,d_1,d_2)=(0,1,1),$$

because its coefficient in $L_2$ is

$$\sum_{i=s_{j-1}+1}^{s_j}i>0.$$

Suppose $d_{t+1}=d_t+d_{t-1}$. Applying (1) as $x\to+\infty$ gives

$$2d_{t+1}-d_{t-1} \le d_{t+2} \le d_t+d_{t+1}.$$

The two bounds coincide because

$$2d_{t+1}-d_{t-1}=d_t+d_{t+1}.$$

Hence $d_{t+2}=d_t+d_{t+1}$, and induction yields

$$\deg_xL_t= \begin{cases} F_{t+1},&x=m_j,\\ F_t,&x=b_j. \end{cases} \tag{3}$$

These conclusions hold for every positive-integer specialization of all remaining parameters. The source's Theorems 3.11 and 3.15 establish that $L_t$ is a polynomial in the full parameter list. Any coefficient of a higher power of $x$ would therefore be a polynomial in the remaining parameters that vanishes on the entire positive-integer lattice, hence vanishes identically. Conversely, each positive specialization already attains the degrees in (3). Thus these are the degrees of the full multivariate polynomials.

Finally,

$$\gamma_n(w)=|\Gamma^{n-1}(w)|,\qquad \ell_n(w)=|\mathcal L^{n-1}(w)|.$$

Substituting $t=n-1$ into (3) proves

$$\deg_{m_j}\gamma_n(w) = \deg_{m_j}\ell_n(w) = F_n,$$

and

$$\deg_{b_j}\gamma_n(w) = \deg_{b_j}\ell_n(w) = F_{n-1},$$

for every $1\le j\le k$ and every $n\ge1$.