Fibonacci Enumeration and Coverage of the Reverse Tree for the Odd-Increment Collatz Variant

Abstract

We study the Collatz variant T: Z_{>0} -> Z_{>0} defined by T(n) = n/2 for even n and T(n) = n+1 for odd n. The reverse tree, obtained by iterating the inverse branches x -> 2x and x -> x-1 (the latter admissible when x is even) from the root 1, encodes the directed graph of the map. We prove two results. (1) Fibonacci enumeration: if L_n denotes the set of positive integers whose orbit first reaches 1 in exactly n steps, then |L_n| = F_{n+1}, where F_k is the Fibonacci sequence. (2) Coverage: every positive integer lies in exactly one layer L_n, so the reverse tree covers all of Z_{>0}. The coverage proof uses an infinite descent argument: any m > 1 is strictly decreased by at most two applications of T. The enumeration is established by a bijective decomposition of each layer into even and odd components. Both results are elementary and complete.