Fibonacci Enumeration of Residue Classes via Forbidden Binary Factors

Abstract

Binary words avoiding adjacent ones are counted by Fibonacci numbers. We identify a natural residue-class enumeration in which this classical word count arises from parity data of the shortcut $3n+1$ map. For an odd starting value, we introduce a local cut time: the first index at which the trajectory enters the residue class $3$ modulo $4$ immediately after an even term. For each finite cut time, the starting values realizing it form a union of complete residue classes modulo a power of two, and the number of these classes is given by an explicit Fibonacci formula. The key step is a recoding of the cut condition as avoidance of the binary factor $11$ in the free part of a parity word. An explicit comparison with the endpoint conventions of the author's 2014 block construction, including the terminal blocks ending at $1$, shows that the resulting residue-class counts prove the two Fibonacci formulas conjectured there in their complete-class form. The construction is a two-state regular-language enumeration; a related theorem of Reyes Jiménez has the bitwise-complementary forbidden-factor formulation $00$.

arXiv comment11 pages, 1 table. This article proves the Fibonacci conjecture from the 2014 version 1412.0519v1