Weight preservation for Fibonacci recurrences

The claim follows from an orbit-fiber counting identity, valid much more generally than the Fibonacci recurrence.

For $\varepsilon\in\{1,-1\}$, let

$$A_\varepsilon= \begin{pmatrix}0&1\\1&\varepsilon\end{pmatrix}.$$

The Fibonacci recurrence and its parity transform act on initial-condition pairs by

$$(a_j,a_{j+1}) \longmapsto (a_{j+1},a_j+\varepsilon a_{j+1}) =A_\varepsilon(a_j,a_{j+1}).$$

Since $\det A_\varepsilon=-1$, this is a permutation of

$$X_s=(\mathbb Z/s\mathbb Z)^2$$

for every $s\ge1$. Its permutation orbits are precisely the periods modulo $s$, and orbit cardinality equals period length.

For $d\mid m$, coordinatewise reduction

$$\pi:X_m\longrightarrow X_d$$

commutes with both recurrence actions:

$$\pi A_{\varepsilon,m}=A_{\varepsilon,d}\pi.$$

Every fiber has cardinality

$$|\pi^{-1}(x)|=(m/d)^2.$$

Fix an orbit $O\subset X_d$ of length $\ell$. Its full inverse image is invariant under $A_{\varepsilon,m}$, so it decomposes into disjoint orbits

$$\pi^{-1}(O)=O_1\sqcup\cdots\sqcup O_r.$$

Each $O_i$ maps onto $O$, since its image is a nonempty invariant subset of a single transitive orbit. Thus the $O_i$ are exactly all periods modulo $m$ reducing to the chosen period modulo $d$.

Counting the inverse image yields

$$\sum_{i=1}^r|O_i| = |\pi^{-1}(O)| = \ell\left(\frac md\right)^2.$$

Dividing by $m^2$ gives precisely

$$\sum_{i=1}^r w_m(O_i) = \sum_{i=1}^r\frac{|O_i|}{m^2} = \frac{\ell}{d^2} = w_d(O).$$

More generally, if $A$ is any integral $r\times r$ matrix whose determinant is coprime to $m$, then for every $d\mid m$ and every orbit $O$ modulo $d$,

$$\sum_{\substack{O'\text{ orbit modulo }m\O'\bmod d=O}} \frac{|O'|}{m^r} = \frac{|O|}{d^r}.$$

Thus orbit-weight preservation holds for every invertible integral linear recurrence in every dimension.