Introduction
Nested recurrences are recurrences in which values at earlier indices occur inside the arguments of the sequence. The classical Hofstadter Q Q Q -sequence is defined by
Q ( n ) = Q ( n − Q ( n − 1 ) ) + Q ( n − Q ( n − 2 ) ) , Q ( 1 ) = Q ( 2 ) = 1 , (1) Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)), \qquad Q(1) = Q(2) = 1, \tag*{(1)} Q ( n ) = Q ( n − Q ( n − 1 )) + Q ( n − Q ( n − 2 )) , Q ( 1 ) = Q ( 2 ) = 1 , (1)
and was introduced in Gödel, Escher, Bach [1 ] . The two recurrences below add a second layer, in which the number of applications of an inner map is itself a previous sequence value. We call this a meta-nested recurrence .
The surrounding literature contains several Conway-type and Hofstadter-type recurrences, including the variants studied by Mallows [2 ] , Kubo and Vakil [3 ] , Tanny [4 ] , and Grytczuk [5 ] . Isgur and Rahman [6 ] study a fixed-depth family containing Grytczuk’s example, prove generalized Fibonacci anchor identities, and ask whether the normalized sequences converge. § 10 proves convergence for their depth-two case and gives its sharp error order. The slow-growth property and the Fibonacci anchors are known. Our proof includes an independent word derivation, so that the asymptotic argument is self-contained. Pascal-word methods and their connection with Conway’s sequence also appear in Janvresse, de la Rue and Velenik [7 ] .
Fixed iteration counts occur in other families, including Cloitre’s arithmetical solutions [8 ] . In (2) and (3) , the iteration depth instead depends on the preceding sequence value. Cloitre’s scaling approach [9 ] relates geometric anchor sequences to linear limits for slow nested recurrences. For the variable-depth sequence C C C , we prove an equivalent convergence criterion in terms of selected inner-orbit steps.
The paper has two purposes. First, it records complete results for the Campbell example and the global golden structure of the Cloitre example. Second, it isolates the remaining asymptotic problem in a form that can be checked locally, namely a negative landing-jump condition in the interiors of the Fibonacci intervals. A separate dispersion criterion gives a conditional rate of convergence. The proofs of the golden structure and of the collars are elementary. A finite exact computation gives a numerical tail bound, and the maximum principle extends it to all later indices. Along inverse rays of the map x ↦ C ( x ) x \mapsto C(x) x ↦ C ( x ) , the normalized sequence converges unconditionally, while the full variable-depth limit remains open.
Definitions
Definition 1 (Campbell recurrence). Let b ( 1 ) = 1 b(1)=1 b ( 1 ) = 1 . For n ≥ 2 n \ge2 n ≥ 2 put
T n ( x ) = n − b ( x ) , b ( n ) = T n b ( n − 1 ) ( n − 1 ) . (2) T_n(x)=n-b(x), \qquad b(n)=T_n^{b(n-1)}(n-1). \tag*{(2)} T n ( x ) = n − b ( x ) , b ( n ) = T n b ( n − 1 ) ( n − 1 ) . (2) where the exponent denotes exactly that many applications of T n T_n T n .
Definition 2 (Cloitre recurrence). Let C ( 1 ) = C ( 2 ) = 1 C(1)=C(2)=1 C ( 1 ) = C ( 2 ) = 1 . For n ≥ 3 n \ge3 n ≥ 3 put
T n ( x ) = n − C ( x ) , g = T n C ( n − 1 ) ( n − 1 ) , C ( n ) = C ( g ) + C ( n − g ) . (3) T_n(x)=n-C(x), \qquad g=T_n^{C(n-1)}(n-1), \qquad C(n)=C(g)+C(n-g). \tag*{(3)} T n ( x ) = n − C ( x ) , g = T n C ( n − 1 ) ( n − 1 ) , C ( n ) = C ( g ) + C ( n − g ) . (3) The prescribed depth is part of the definition. The split is not an arbitrary periodic point of the inner map.
We use F 0 = 0 F_0=0 F 0 = 0 , F 1 = 1 F_1=1 F 1 = 1 , F j + 1 = F j + F j − 1 F_{j+1}=F_j+F_{j-1} F j + 1 = F j + F j − 1 and
α = 5 − 1 2 = 1 ϕ , G ( n ) = ⌊ α ( n + 1 ) ⌋ . \alpha=\frac{\sqrt{5}-1}{2}=\frac{1}{\phi}, \qquad G(n)=\lfloor\alpha(n+1)\rfloor. α = 2 5 − 1 = ϕ 1 , G ( n ) = ⌊ α ( n + 1 )⌋ .
Lemma 3 (Well-definedness and cyclic selection). The sequence C C C is well-defined and satisfies
⌈ n / 2 ⌉ ≤ C ( n ) ≤ n − 1 ( n ≥ 2 ) , C ( n ) ≤ 3 n / 4 ( n ≥ 2 ) , C ( n ) ≥ 3 n / 5 ( n ≥ 3 ) . \lceil n/2\rceil\le C(n) \le n-1 \quad(n \ge2), \qquad C(n) \le3n/4 \quad(n \ge2), \qquad C(n) \ge3n/5 \quad(n \ge3). ⌈ n /2 ⌉ ≤ C ( n ) ≤ n − 1 ( n ≥ 2 ) , C ( n ) ≤ 3 n /4 ( n ≥ 2 ) , C ( n ) ≥ 3 n /5 ( n ≥ 3 ) . For every n ≥ 3 n \ge3 n ≥ 3 , g ( n ) g(n) g ( n ) lies on the cycle reached from n − 1 n-1 n − 1 .
The proof is in Appendix § 16 .§ 1 . In particular, cycle reduction computes the prescribed iterate exactly, without changing the starting point or the iteration depth.
Worked examples
The definition of C C C is short, but each value is obtained through a small dynamical computation. We describe this computation for a few values of n n n , each chosen to show one new feature.
Recall that C ( 1 ) = C ( 2 ) = 1 C(1) = C(2) = 1 C ( 1 ) = C ( 2 ) = 1 and that, for n ≥ 3 n \ge3 n ≥ 3 ,
T n ( y ) = n − C ( y ) , h n = C ( n − 1 ) , g ( n ) = T n h n ( n − 1 ) , C ( n ) = C ( g ( n ) ) + C ( n − g ( n ) ) . T_n(y) = n - C(y), \qquad h_n = C(n-1), \qquad g(n) = T_n^{h_n}(n-1), \qquad C(n) = C(g(n)) + C(n-g(n)). T n ( y ) = n − C ( y ) , h n = C ( n − 1 ) , g ( n ) = T n h n ( n − 1 ) , C ( n ) = C ( g ( n )) + C ( n − g ( n )) .
Since 1 ≤ C ( y ) ≤ y 1 \le C(y) \le y 1 ≤ C ( y ) ≤ y , the map T n T_n T n sends { 1 , … , n − 1 } \{1,\ldots,n-1\} { 1 , … , n − 1 } into itself and only uses values of C C C that are already known. We write y r = T n r ( n − 1 ) y_r = T_n^r(n-1) y r = T n r ( n − 1 ) for the orbit of n − 1 n-1 n − 1 . This orbit is eventually periodic. Its entry rank τ n \tau_n τ n is the first r r r for which y r y_r y r lies on a cycle, and p n p_n p n denotes the length of that cycle. For every n ≥ 3 n \ge3 n ≥ 3 one has h n ≥ τ n h_n \ge\tau_n h n ≥ τ n (Lemma 3 ). The point g ( n ) g(n) g ( n ) therefore lies on the cycle and
g ( n ) = y τ n + ( ( h n − τ n ) m o d p n ) . g(n) = y_{\tau_n+((h_n-\tau_n)\bmod p_n)}. g ( n ) = y τ n + (( h n − τ n ) mod p n ) .
In practice one never iterates h n h_n h n times. Once the orbit has reached its cycle, only the residue of h n − τ n h_n-\tau_n h n − τ n modulo p n p_n p n matters.
If the depth h n h_n h n is replaced by 1, then g ( n ) = n − C ( n − 1 ) g(n)=n-C(n-1) g ( n ) = n − C ( n − 1 ) and the recurrence becomes C ( n ) = C ( n − C ( n − 1 ) ) + C ( C ( n − 1 ) ) C(n)=C(n-C(n-1))+C(C(n-1)) C ( n ) = C ( n − C ( n − 1 )) + C ( C ( n − 1 )) . This is the Hofstadter–Conway recurrence a ( n ) = a ( a ( n − 1 ) ) + a ( n − a ( n − 1 ) ) a(n)=a(a(n-1))+a(n-a(n-1)) a ( n ) = a ( a ( n − 1 )) + a ( n − a ( n − 1 )) of A004001 with its two terms exchanged. The sequence C C C follows the same map for C ( n − 1 ) C(n-1) C ( n − 1 ) steps instead of one. Table 1 gives the first values of both sequences together with the data of the computation.
The value n = 4 n=4 n = 4 . The first value where C C C and a a a differ is n = 4 n=4 n = 4 . Since C ( 3 ) = 2 C(3)=2 C ( 3 ) = 2 and C ( 2 ) = 1 C(2)=1 C ( 2 ) = 1 , the orbit of 3 under T 4 ( y ) = 4 − C ( y ) T_4(y)=4-C(y) T 4 ( y ) = 4 − C ( y ) is 3 , 2 , 3 , 2 , … 3,2,3,2,\ldots 3 , 2 , 3 , 2 , … , a cycle of length 2 from the start. Thus τ 4 = 0 \tau_4=0 τ 4 = 0 , p 4 = 2 p_4=2 p 4 = 2 , and the even depth h 4 = C ( 3 ) = 2 h_4=C(3)=2 h 4 = C ( 3 ) = 2 brings the orbit back to y 2 = 3 y_2=3 y 2 = 3 . Hence g ( 4 ) = 3 g(4)=3 g ( 4 ) = 3 and C ( 4 ) = C ( 3 ) + C ( 1 ) = 3 C(4)=C(3)+C(1)=3 C ( 4 ) = C ( 3 ) + C ( 1 ) = 3 . A single step stops at y 1 = 2 y_1=2 y 1 = 2 and gives C ( 2 ) + C ( 2 ) = 2 C(2)+C(2)=2 C ( 2 ) + C ( 2 ) = 2 , which is the value a ( 4 ) = 2 a(4)=2 a ( 4 ) = 2 of the Hofstadter–Conway sequence.
The value n = 10 n=10 n = 10 . Here h 10 = C ( 9 ) = 6 h_{10}=C(9)=6 h 10 = C ( 9 ) = 6 . Since C ( 9 ) = 6 C(9)=6 C ( 9 ) = 6 , C ( 4 ) = 3 C(4)=3 C ( 4 ) = 3 , C ( 7 ) = 5 C(7)=5 C ( 7 ) = 5 and C ( 5 ) = 3 C(5)=3 C ( 5 ) = 3 , the orbit of 9 under T 10 T_{10} T 10 is
9 ↦ 4 ↦ 7 ↦ 5 ↦ 7 ↦ 5 ↦ ⋯ 9 \mapsto4 \mapsto7 \mapsto5 \mapsto7 \mapsto5 \mapsto\cdots 9 ↦ 4 ↦ 7 ↦ 5 ↦ 7 ↦ 5 ↦ ⋯
Table 1. Depth h n = C ( n − 1 ) h_n = C(n - 1) h n = C ( n − 1 ) , entry rank τ n \tau_n τ n , period p n p_n p n , selected point g ( n ) g(n) g ( n ) and value C ( n ) C(n) C ( n ) for 3 ≤ n ≤ 21 3 \le n \le21 3 ≤ n ≤ 21 , compared with the Hofstadter–Conway sequence a a a (A004001). Both sequences start with 1, 1.
After a transient of two steps it enters the 2-cycle { 5 , 7 } \{5, 7\} { 5 , 7 } , so τ 10 = p 10 = 2 \tau_{10} = p_{10} = 2 τ 10 = p 10 = 2 . As h 10 − τ 10 = 4 h_{10} - \tau_{10} = 4 h 10 − τ 10 = 4 is even, the iteration stops at y 2 = 7 y_2 = 7 y 2 = 7 and
C ( 10 ) = C ( 7 ) + C ( 3 ) = 5 + 2 = 7. C(10) = C(7) + C(3) = 5 + 2 = 7. C ( 10 ) = C ( 7 ) + C ( 3 ) = 5 + 2 = 7.
An odd depth would have stopped at 5 and given C ( 5 ) + C ( 5 ) = 6 C(5) + C(5) = 6 C ( 5 ) + C ( 5 ) = 6 . When the cycle has two points, the parity of the depth decides which one is used.
Fibonacci arguments, n = 13 n = 13 n = 13 . For n = 13 n = 13 n = 13 the depth is h 13 = C ( 12 ) = 8 h_{13} = C(12) = 8 h 13 = C ( 12 ) = 8 and the orbit of 12 is
12 ↦ 5 ↦ 10 ↦ 6 ↦ 9 ↦ 7 ↦ 8 ↦ 8 ↦ ⋯ . 12 \mapsto5 \mapsto10 \mapsto6 \mapsto9 \mapsto7 \mapsto8 \mapsto8 \mapsto\cdots. 12 ↦ 5 ↦ 10 ↦ 6 ↦ 9 ↦ 7 ↦ 8 ↦ 8 ↦ ⋯ .
It alternates on both sides of 8 and reaches the fixed point 8 at rank 6 ≤ h 13 6 \le h_{13} 6 ≤ h 13 . Therefore g ( 13 ) = 8 g(13) = 8 g ( 13 ) = 8 and C ( 13 ) = C ( 8 ) + C ( 5 ) = 5 + 3 = 8 C(13) = C(8) + C(5) = 5 + 3 = 8 C ( 13 ) = C ( 8 ) + C ( 5 ) = 5 + 3 = 8 . The same picture holds at every Fibonacci number F k ≥ 8 F_k \ge8 F k ≥ 8 . The value C ( F k − 1 ) = F k − 2 C(F_{k-1}) = F_{k-2} C ( F k − 1 ) = F k − 2 makes F k − 1 F_{k-1} F k − 1 a fixed point of T F k T_{F_k} T F k , the orbit of F k − 1 F_k - 1 F k − 1 ends there, and
C ( F k ) = C ( F k − 1 ) + C ( F k − 2 ) = F k − 2 + F k − 3 = F k − 1 . C(F_k) = C(F_{k-1}) + C(F_{k-2}) = F_{k-2} + F_{k-3} = F_{k-1}. C ( F k ) = C ( F k − 1 ) + C ( F k − 2 ) = F k − 2 + F k − 3 = F k − 1 .
The landing statement of Theorem 7 shows that this happens for every k ≥ 6 k \ge6 k ≥ 6 . The value n = 5 n = 5 n = 5 behaves differently, since the orbit of 4 is the 2-cycle { 2 , 4 } \{2, 4\} { 2 , 4 } and the odd depth h 5 = 3 h_5 = 3 h 5 = 3 selects 2, which still gives C ( 5 ) = C ( 2 ) + C ( 3 ) = 3 C(5) = C(2) + C(3) = 3 C ( 5 ) = C ( 2 ) + C ( 3 ) = 3 .
The first descent, n = 43 n = 43 n = 43 . The sequence C C C is not monotone, and its first descent shows the role of the depth. For n = 43 n = 43 n = 43 the depth is h 43 = C ( 42 ) = 29 h_{43} = C(42) = 29 h 43 = C ( 42 ) = 29 . The orbit of 42 is listed in Table 2 and drawn in Figure 1 . It alternates on both sides of the diagonal with gaps 28, 20, 12, 7, 6, 5, 4 and enters the 2-cycle { 24 , 28 } \{24, 28\} { 24 , 28 } at rank τ 43 = 6 \tau_{43} = 6 τ 43 = 6 . Since h 43 − τ 43 = 23 h_{43} - \tau_{43} = 23 h 43 − τ 43 = 23 is odd, the iteration stops at y 7 = 24 y_7 = 24 y 7 = 24 , and
Figure 1. The orbit of 42 under T 43 ( y ) = 43 − C ( y ) T_{43}(y) = 43 - C(y) T 43 ( y ) = 43 − C ( y ) . The small dots are the points ( y , T 43 ( y ) ) (y,T_{43}(y)) ( y , T 43 ( y )) for 10 ≤ y ≤ 42 10 \le y \le42 10 ≤ y ≤ 42 , the grey line is the diagonal, and the two large dots mark the 2-cycle { 24 , 28 } \{24, 28\} { 24 , 28 } .
C ( 43 ) = C ( 24 ) + C ( 19 ) = 15 + 13 = 28 < 29 = C ( 42 ) . C(43) = C(24) + C(19) = 15 + 13 = 28 < 29 = C(42). C ( 43 ) = C ( 24 ) + C ( 19 ) = 15 + 13 = 28 < 29 = C ( 42 ) .
The other point of the cycle would give C ( 28 ) + C ( 15 ) = 19 + 10 = 29 C(28) + C(15) = 19 + 10 = 29 C ( 28 ) + C ( 15 ) = 19 + 10 = 29 , and a single step would also give 29, since y 1 = 14 y_1 = 14 y 1 = 14 and C ( 14 ) + C ( 29 ) = 9 + 20 = 29 C(14) + C(29) = 9 + 20 = 29 C ( 14 ) + C ( 29 ) = 9 + 20 = 29 . The descent at n = 43 n = 43 n = 43 comes from the parity of the depth alone. The first increment larger than 1 occurs earlier, at n = 26 n = 26 n = 26 , where C ( 25 ) = 16 C(25) = 16 C ( 25 ) = 16 and C ( 26 ) = 18 C(26) = 18 C ( 26 ) = 18 .
Table 2. The orbit of 42 under T 43 T_{43} T 43 . From rank 6 on it alternates between 28 and 24.
Longer cycles. Cycles of length 1 and 2 are the only ones for n < 68 n < 68 n < 68 . The first cycles of length 4, 6, 3 and 5 appear at n = 68 n = 68 n = 68 , 120, 126 and 196. For n = 196 n = 196 n = 196 the orbit of 195 enters the 5-cycle (120, 116, 117, 118, 115) at rank 8. The depth is h 196 = C ( 195 ) = 131 h_{196} = C(195) = 131 h 196 = C ( 195 ) = 131 and 131 − 8 ≡ 3 ( m o d 5 ) 131 - 8 \equiv3 \pmod{5} 131 − 8 ≡ 3 ( mod 5 ) , so the iteration stops three points after the entry, at y 11 = 118 y_{11} = 118 y 11 = 118 , and C ( 196 ) = C ( 118 ) + C ( 78 ) = 81 + 53 = 134 C(196) = C(118) + C(78) = 81 + 53 = 134 C ( 196 ) = C ( 118 ) + C ( 78 ) = 81 + 53 = 134 . The five points of this cycle would give the five values 129, 132, 131, 134, 130.
Campbell's recurrence
Theorem 4 (Explicit formula). For every n ≥ 2 n \ge2 n ≥ 2 , let s s s be the unique power of three in the indicated range. Then
b ( n ) = { min ( n − s , 3 s ) , n even and 2 s ≤ n < 6 s , max ( 2 s , n − 3 s ) , n odd and 3 s ≤ n < 9 s . (4) b(n) =
\begin{cases}
\min(n-s,3s), & n\ \text{even and } 2s \le n < 6s,\\
\max(2s,n-3s), & n\ \text{odd and } 3s \le n < 9s.
\end{cases} \tag*{(4)} b ( n ) = { min ( n − s , 3 s ) , max ( 2 s , n − 3 s ) , n even and 2 s ≤ n < 6 s , n odd and 3 s ≤ n < 9 s . (4)
Proof. The twelve orbit rows in Appendix § 18 give a strong induction proof, including the parity of the prescribed depth. In particular, the orbit agrees with its two-periodic tail from rank 4. Even depth selects rank 4, and odd depth selects rank 5.
Corollary 5. The recurrence (2) is globally well-defined. Its inner orbit has transient length at most four before entering a fixed point or a two-cycle, and
b ( 3 n ) = 3 b ( n ) ( n ≥ 2 ) , lim inf n → ∞ b ( n ) n = 2 5 , lim sup n → ∞ b ( n ) n = 3 4 . b(3n) = 3b(n) \quad(n \ge2), \qquad\liminf_{n \to\infty} \frac{b(n)}{n} = \frac{2}{5}, \qquad\limsup_{n \to\infty} \frac{b(n)}{n} = \frac{3}{4}. b ( 3 n ) = 3 b ( n ) ( n ≥ 2 ) , n → ∞ lim inf n b ( n ) = 5 2 , n → ∞ lim sup n b ( n ) = 4 3 . In particular, b ( n ) / n b(n)/n b ( n ) / n does not converge.
The global golden structure of C C C
The main comparison sequence is the Hofstadter G G G -sequence G ( n ) G(n) G ( n ) . Its identity G ( n ) = n − G ( G ( n − 1 ) ) G(n) = n - G(G(n - 1)) G ( n ) = n − G ( G ( n − 1 )) follows directly from the rotation identity for α \alpha α and uniquely determines the sequence from its initial values.
Theorem 6 (Golden lower bound and equality set). For every n ≥ 1 n \ge1 n ≥ 1 ,
C ( n ) ≥ G ( n ) . C(n) \ge G(n). C ( n ) ≥ G ( n ) . Moreover, equality holds exactly on
Z = { F j , F j + 1 : j ≥ 2 } ∪ { F j − 1 : j ≥ 3 odd } ∪ { 11 , 24 , 25 , 59 } . (5) Z = \{F_j, F_j + 1 : j \ge2\} \cup\{F_j - 1 : j \ge3\ \text{odd}\} \cup\{11, 24, 25, 59\}. \tag*{(5)} Z = { F j , F j + 1 : j ≥ 2 } ∪ { F j − 1 : j ≥ 3 odd } ∪ { 11 , 24 , 25 , 59 } . (5)
Theorem 7 (Fibonacci upper cap and landing). If F j ≤ n < F j + 1 F_j \le n < F_{j+1} F j ≤ n < F j + 1 and j ≥ 3 j \ge3 j ≥ 3 , then
C ( n ) ≤ U ( n ) : = min ( n − F j − 2 , F j ) . (6) C(n) \le U(n) := \min(n-F_{j-2},F_j). \tag*{(6)} C ( n ) ≤ U ( n ) := min ( n − F j − 2 , F j ) . (6) Consequently,
C ( F j ) = F j − 1 ( j ≥ 2 ) , C ( F j − 1 ) = F j − 1 ( j ≥ 5 ) , C ( F j + 1 ) = F j − 1 + 1 ( j ≥ 3 ) . (7) \begin{aligned}
C(F_j) &= F_{j-1} && (j \ge2),\\
C(F_j-1) &= F_{j-1} && (j \ge5),\\
C(F_j+1) &= F_{j-1}+1 && (j \ge3). \tag*{(7)}
\end{aligned} C ( F j ) C ( F j − 1 ) C ( F j + 1 ) = F j − 1 = F j − 1 = F j − 1 + 1 ( j ≥ 2 ) , ( j ≥ 5 ) , ( j ≥ 3 ) . (7) For k ≥ 6 k \ge6 k ≥ 6 , every orbit of T F k T_{F_k} T F k on [ 1 , F k − 1 ] [1,F_k-1] [ 1 , F k − 1 ] eventually reaches the fixed point F k − 1 F_{k-1} F k − 1 . In particular, the prescribed depth in (3) selects that point.
The cap U U U has the same block formula as Peter Bala’s sequence A356988. The two block descriptions in its OEIS entry [10 ] meet at the Lucas number F j + F j − 2 F_j+F_{j-2} F j + F j − 2 . This identification rests on that block formula, not on the nested recurrence that defines A356988.
Corollary 8.
lim inf n → ∞ C ( n ) n = α . (8) \liminf_{n\to\infty}\frac{C(n)}{n}=\alpha. \tag*{(8)} n → ∞ lim inf n C ( n ) = α . (8) The full limit is not established by these results.
Proof of Theorems 6 and 7 and of the corollary. Appendix B gives a simultaneous induction for the lower bound, for the implication C ( x ) = G ( x ) ⇒ x ∈ Z C(x)=G(x)\Rightarrow x\in Z C ( x ) = G ( x ) ⇒ x ∈ Z and for the cap, strengthened at the changes of slope of U U U . It displays the twenty-four initial values and all exceptional child pairs. The reverse inclusion in the equality set and the Fibonacci landing statement then follow from the comparison and capture bounds. The corollary follows from the lower bound and the anchors C ( F j ) = F j − 1 C(F_j)=F_{j-1} C ( F j ) = F j − 1 .
Theorem 9 (The left Fibonacci plateau). For k ≥ 8 k \ge8 k ≥ 8 , put w k = ⌊ ( 2 k − 9 ) / 3 ⌋ w_k=\lfloor(2k-9)/3\rfloor w k = ⌊( 2 k − 9 ) /3 ⌋ . Then
C ( F k − u ) = F k − 1 ⟺ 0 ≤ u ≤ w k ( 0 ≤ u ≤ F k − 2 , u ∈ Z ) . C(F_k-u)=F_{k-1}\quad\Longleftrightarrow\quad0\le u\le w_k\qquad(0\le u\le F_{k-2},\ u\in Z). C ( F k − u ) = F k − 1 ⟺ 0 ≤ u ≤ w k ( 0 ≤ u ≤ F k − 2 , u ∈ Z ) . Moreover,
C ( F k − w k − 1 ) = F k − 1 − 1 , min { n ≥ 1 ∣ C ( n ) = F k − 1 } = F k − w k . C(F_k-w_k-1)=F_{k-1}-1,\qquad\min\{n\ge1\mid C(n)=F_{k-1}\}=F_k-w_k. C ( F k − w k − 1 ) = F k − 1 − 1 , min { n ≥ 1 ∣ C ( n ) = F k − 1 } = F k − w k .
The width w k w_k w k increases by one exactly when F k − 1 F_{k-1} F k − 1 is odd, so it grows linearly in k k k . The proof is an induction on k k k and is given in Appendix C.
Fibonacci collars and profile renormalization
For any j ≥ 2 j\ge2 j ≥ 2 and integer u u u with F j + u ≥ 1 F_j+u\ge1 F j + u ≥ 1 , define
P j ( u ) = C ( F j + u ) − F j − 1 , D j ( u ) = P j ( u ) − max ( 0 , u ) , E j ( u ) = − D j ( u ) . P_j(u)=C(F_j+u)-F_{j-1},\qquad D_j(u)=P_j(u)-\max(0,u),\qquad E_j(u)=-D_j(u). P j ( u ) = C ( F j + u ) − F j − 1 , D j ( u ) = P j ( u ) − max ( 0 , u ) , E j ( u ) = − D j ( u ) .
For the capture theorem, fix k ≥ 6 k\ge6 k ≥ 6 , write n = F k + t ≥ 3 n=F_k+t\ge3 n = F k + t ≥ 3 with t ∈ Z t\in Z t ∈ Z , and put A = F k − 1 A=F_{k-1} A = F k − 1 .
Theorem 10 (Collar capture and profile identity). Every cycle of T n T_n T n is contained in
I k , t = [ A + min ( 0 , t ) , A + max ( 0 , t ) ] , (9) I_{k,t}=[A+\min(0,t),A+\max(0,t)], \tag*{(9)} I k , t = [ A + min ( 0 , t ) , A + max ( 0 , t )] , (9) and every orbit eventually enters this interval. Hence every cycle has period at most ∣ t ∣ + 1 |t|+1 ∣ t ∣ + 1 . If the selected split is a = A + s a=A+s a = A + s , then
P k ( t ) = P k − 1 ( s ) + P k − 2 ( t − s ) , P_k(t)=P_{k-1}(s)+P_{k-2}(t-s), P k ( t ) = P k − 1 ( s ) + P k − 2 ( t − s ) , D k ( t ) = D k − 1 ( s ) + D k − 2 ( t − s ) ≤ 0 , (10) D_k(t)=D_{k-1}(s)+D_{k-2}(t-s)\le0, \tag*{(10)} D k ( t ) = D k − 1 ( s ) + D k − 2 ( t − s ) ≤ 0 , (10) with s ∈ [ min ( 0 , t ) , max ( 0 , t ) ] ∩ Z s\in[\min(0,t),\max(0,t)]\cap\mathbb{Z} s ∈ [ min ( 0 , t ) , max ( 0 , t )] ∩ Z .
Proof. Put B = F k − 2 B=F_{k-2} B = F k − 2 , so n − B = A + t n-B=A+t n − B = A + t , and write I = [ ℓ , h ] I=[\ell,h] I = [ ℓ , h ] for (9) . The cones (34) hold at the anchor ( A , B ) (A,B) ( A , B ) for every actual argument 1 ≤ x < n 1\le x<n 1 ≤ x < n . They make I ∩ [ 1 , n − 1 ] I\cap[1,n-1] I ∩ [ 1 , n − 1 ] invariant. For u ≥ 1 u\ge1 u ≥ 1 , they also give
T n ( ℓ − u ) ∈ [ ℓ , h + u − 1 ] , T n ( h + u ) ∈ [ ℓ − u , h ] T_n(\ell-u)\in[\ell,h+u-1],\qquad T_n(h+u)\in[\ell-u,h] T n ( ℓ − u ) ∈ [ ℓ , h + u − 1 ] , T n ( h + u ) ∈ [ ℓ − u , h ]
whenever the argument belongs to the domain. An exterior point therefore enters I I I or switches sides, with integer distance decreasing within at most two steps. This proves capture for either sign of t t t , even if the anchor lies outside the domain. A cycle has distinct integer points, so its period is at most ∣ t ∣ + 1 |t|+1 ∣ t ∣ + 1 .
The selected split is cyclic by Lemma 3 , hence a = A + s a=A+s a = A + s with min ( 0 , t ) ≤ s ≤ max ( 0 , t ) \min(0,t)\le s\le\max(0,t) min ( 0 , t ) ≤ s ≤ max ( 0 , t ) . Its complement is n − a = F k − 2 + ( t − s ) n-a=F_{k-2}+(t-s) n − a = F k − 2 + ( t − s ) . Both are positive actual arguments. Substitution in (3) gives the first profile identity. The offsets s s s and t − s t-s t − s have the same weak sign as t t t , so
max ( 0 , s ) + max ( 0 , t − s ) = max ( 0 , t ) , \max(0,s)+\max(0,t-s)=\max(0,t), max ( 0 , s ) + max ( 0 , t − s ) = max ( 0 , t ) ,
which gives the identity for D k D_k D k . The global cap U U U of Theorem 7 , with U ( 1 ) = 1 U(1)=1 U ( 1 ) = 1 , is nondecreasing, has increments zero or one, and satisfies U ( F j ) = F j − 1 U(F_j)=F_{j-1} U ( F j ) = F j − 1 . Consequently, for every integer u u u with F j + u ≥ 1 F_j+u\ge1 F j + u ≥ 1 ,
C ( F j + u ) ≤ U ( F j + u ) ≤ F j − 1 + max ( 0 , u ) . C(F_j+u)\le U(F_j+u)\le F_{j-1}+\max(0,u). C ( F j + u ) ≤ U ( F j + u ) ≤ F j − 1 + max ( 0 , u ) .
Applying this bound to the two child offsets gives their nonpositive defects and completes the proof. □
Corollary 11 (Sublinear-width convergence). For arbitrary integer offsets with t k / F k → 0 t_k/F_k\to0 t k / F k → 0 , including negative offsets,
C ( F k + t k ) F k + t k ⟶ α . \frac{C(F_k+t_k)}{F_k+t_k}\longrightarrow\alpha. F k + t k C ( F k + t k ) ⟶ α . For every fixed integer t t t , the periods are uniformly bounded in k k k . For every fixed integer t t t , for all sufficiently large k k k ,
C ( F k + t ) = F k − 1 + max ( 0 , t ) . C(F_k+t)=F_{k-1}+\max(0,t). C ( F k + t ) = F k − 1 + max ( 0 , t ) .
For the first statement the lower bound and the cap suffice, since on either side of F k F_k F k the cap differs from F k − 1 F_{k-1} F k − 1 by at most ∣ t k ∣ + O ( 1 ) |t_k| + O(1) ∣ t k ∣ + O ( 1 ) . The left plateau of Theorem 9 and the right collar of Proposition 12 give the fixed-offset identity.
For each fixed integer t t t , applying this identity at level k − 1 k-1 k − 1 to the finitely many offsets min ( 0 , t ) ≤ s ≤ max ( 0 , t ) \min(0,t) \le s \le\max(0,t) min ( 0 , t ) ≤ s ≤ max ( 0 , t ) gives, for all sufficiently large k k k ,
T F k + t ( F k − 1 + s ) = F k − 1 + t − max ( 0 , s ) . T_{F_k+t}(F_{k-1}+s) = F_{k-1}+t-\max(0,s). T F k + t ( F k − 1 + s ) = F k − 1 + t − max ( 0 , s ) .
Thus, if t < 0 t<0 t < 0 , every orbit reaches the unique fixed point F k − 1 + t F_{k-1}+t F k − 1 + t ; if t ≥ 0 t\ge0 t ≥ 0 , the captured map is the reflection s ↦ t − s s \mapsto t-s s ↦ t − s , so every cycle has period one or two.
For the five-cycle at 196 in § 2.1 , the offsets from F 11 = 89 F_{11}=89 F 11 = 89 are 31 → 27 → 28 → 29 → 26 → 31 31 \to27 \to28 \to29 \to26 \to31 31 → 27 → 28 → 29 → 26 → 31 . The profile values E 11 E_{11} E 11 along it are ( 6 , 3 , 5 , 3 , 5 ) (6,3,5,3,5) ( 6 , 3 , 5 , 3 , 5 ) .
Proposition 12 (A logarithmic right collar). For every k ≥ 8 k \ge8 k ≥ 8 ,
C ( F k + t ) = F k − 1 + t ( 0 ≤ t ≤ ⌊ k − 8 6 ⌋ , t ∈ Z ) . C(F_k+t)=F_{k-1}+t \qquad\left(0 \le t \le\left\lfloor\frac{k-8}{6} \right\rfloor,\ t \in\mathbb{Z}\right). C ( F k + t ) = F k − 1 + t ( 0 ≤ t ≤ ⌊ 6 k − 8 ⌋ , t ∈ Z ) .
The width grows logarithmically with F k F_k F k . The proof in Appendix § 17 shows that a first positive defect would propagate to the levels k − 2 k-2 k − 2 and k − 4 k-4 k − 4 and force F k − 1 F_{k-1} F k − 1 , F k − 3 F_{k-3} F k − 3 and F k − 5 F_{k-5} F k − 5 to have the same parity, whereas exactly one of them is even.
For 0 ≤ t ≤ F k − 1 0 \le t \le F_{k-1} 0 ≤ t ≤ F k − 1 , write a captured point as F k − 1 + u F_{k-1}+u F k − 1 + u . The inner map in these coordinates is
u ⟼ t − u + E k − 1 ( u ) . (11) u \longmapsto t-u+E_{k-1}(u). \tag*{(11)} u ⟼ t − u + E k − 1 ( u ) . (11)
For a five-cycle this gives
2 u 0 = t + E 0 − E 1 + E 2 − E 3 + E 4 , 2 ∑ i = 0 4 u i = 5 t + ∑ i = 0 4 E i . (12) 2u_0=t+E_0-E_1+E_2-E_3+E_4,\qquad2\sum_{i=0}^{4}u_i=5t+\sum_{i=0}^{4}E_i. \tag*{(12)} 2 u 0 = t + E 0 − E 1 + E 2 − E 3 + E 4 , 2 i = 0 ∑ 4 u i = 5 t + i = 0 ∑ 4 E i . (12)
Here E i = E k − 1 ( u i ) E_i=E_{k-1}(u_i) E i = E k − 1 ( u i ) . These closure identities hold for every five-cycle. They do not classify the cycles, since the defect word and the phase selected by the prescribed start and depth remain to be determined.
An interior landing-jump criterion
Write g ( n ) = T n C ( n − 1 ) ( n − 1 ) g(n)=T_n^{C(n-1)}(n-1) g ( n ) = T n C ( n − 1 ) ( n − 1 ) and define
d ( n ) = C ( n ) n − α , e − ( n ) = max ( 0 , − e ( n ) ) , e ( n ) = T n ( g ( n ) ) − g ( n ) = n − C ( g ( n ) ) − g ( n ) . (13) \begin{aligned}
d(n)&=\frac{C(n)}{n}-\alpha,\qquad e_-(n)=\max(0,-e(n)),\\
e(n)&=T_n(g(n))-g(n)=n-C(g(n))-g(n). \tag*{(13)}
\end{aligned} d ( n ) e ( n ) = n C ( n ) − α , e − ( n ) = max ( 0 , − e ( n )) , = T n ( g ( n )) − g ( n ) = n − C ( g ( n )) − g ( n ) . (13)
The displacement e ( n ) e(n) e ( n ) is an inner-orbit step, whereas d ( n ) d(n) d ( n ) measures the outer sequence’s relative error. For F j ≤ x < F j + 1 F_j \le x < F_{j+1} F j ≤ x < F j + 1 put
q ( x ) = x − F j F j − 1 ∈ [ 0 , 1 ) . q(x)=\frac{x-F_j}{F_{j-1}}\in[0,1). q ( x ) = F j − 1 x − F j ∈ [ 0 , 1 ) .
For 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 , define the nonnegative localized limsup
E − ( δ ) = lim sup n → ∞ 1 { δ ≤ g ( n ) ≤ 1 − δ } e − ( n ) n . E_-(\delta)=\limsup_{n\to\infty}1_{\{\delta\leq g(n)\leq1-\delta\}}\frac{e_-(n)}{n}. E − ( δ ) = n → ∞ lim sup 1 { δ ≤ g ( n ) ≤ 1 − δ } n e − ( n ) .
This definition gives zero if only finitely many indices meet the restriction.
Cloitre [9 Theorem 3] derives linear limits from geometric anchors for slow recurrences under bounded-error splitting hypotheses. His Proposition 24 treats an alternately perturbed Conway recurrence under geometric-anchor and sublinear adjacent-jump hypotheses. Neither set of hypotheses has been established for the variable-depth sequence C C C here. Our criterion instead concerns only the negative part of the prescribed inner landing step, and it does not require a bound on every adjacent difference C ( n ) − C ( n − 1 ) C(n)-C(n-1) C ( n ) − C ( n − 1 ) .
By Lemma 3 , the selected point is cyclic. The capture bounds (36) give, with inherited endpoint labels,
F k − 1 ≤ g ( n ) ≤ F k , F k − 2 ≤ n − g ( n ) ≤ F k − 1 ( F k ≤ n < F k + 1 , n ≥ 8 ) . (14) F_{k-1}\leq g(n)\leq F_k,\qquad F_{k-2}\leq n-g(n)\leq F_{k-1}\quad(F_k\leq n<F_{k+1},\ n\geq8). \tag*{(14)} F k − 1 ≤ g ( n ) ≤ F k , F k − 2 ≤ n − g ( n ) ≤ F k − 1 ( F k ≤ n < F k + 1 , n ≥ 8 ) . (14)
Theorem 13. Put L = lim sup n → ∞ d ( n ) L=\limsup_{n\to\infty}d(n) L = lim sup n → ∞ d ( n ) and E − = lim sup n → ∞ e − ( n ) / n E_-=\limsup_{n\to\infty}e_-(n)/n E − = lim sup n → ∞ e − ( n ) / n . Then
0 ≤ L ≤ φ E − . (15) 0\leq L\leq\varphi E_-. \tag*{(15)} 0 ≤ L ≤ φ E − . (15) The following conditions are equivalent.
C ( n ) / n ⟶ α C(n)/n\longrightarrow\alpha C ( n ) / n ⟶ α .
e − ( n ) = o ( n ) e_-(n)=o(n) e − ( n ) = o ( n ) .
E − ( δ ) = 0 E_-(\delta)=0 E − ( δ ) = 0 for every δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) .
If L > 0 L>0 L > 0 , there is a δ > 0 \delta>0 δ > 0 such that E − ( δ ) ≥ α L E_-(\delta)\geq\alpha L E − ( δ ) ≥ α L .
Proof. The exact splitting identity gives
d ( n ) = g ( n ) n d ( g ( n ) ) + n − g ( n ) n d ( n − g ( n ) ) . (16) d(n)=\frac{g(n)}{n}d(g(n))+\frac{n-g(n)}{n}d(n-g(n)). \tag*{(16)} d ( n ) = n g ( n ) d ( g ( n )) + n n − g ( n ) d ( n − g ( n )) . (16)
Both weights stay bounded away from zero by (14) . Hence, along any subsequence with d ( n ) → L d(n)\to L d ( n ) → L , both child errors tend to L L L , since each is at most L + o ( 1 ) L+o(1) L + o ( 1 ) and a fixed deficit in either child would force a fixed deficit in the parent.
Suppose L > 0 L>0 L > 0 . Set θ ( n ) = n / F k \theta(n)=n/F_k θ ( n ) = n / F k when F k ≤ n < F k + 1 F_k\leq n<F_{k+1} F k ≤ n < F k + 1 . Among the cluster points ( L , θ ) (L,\theta) ( L , θ ) of ( d ( n ) , θ ( n ) ) (d(n),\theta(n)) ( d ( n ) , θ ( n )) , choose one with minimum second coordinate θ ∗ \theta_* θ ∗ . Take a subsequence realizing it, and pass further so that g ( n ) / n → λ g(n)/n\to\lambda g ( n ) / n → λ . Since d ( g ( n ) ) → L > 0 d(g(n))\to L>0 d ( g ( n )) → L > 0 but Fibonacci endpoints have error tending to zero, the child lies strictly between F k − 1 F_{k-1} F k − 1 and F k F_k F k eventually. Its canonical phase is therefore g ( n ) / F k − 1 g(n)/F_{k-1} g ( n ) / F k − 1 , and minimality yields
θ ∗ ≤ lim g ( n ) F k − 1 = λ φ θ ∗ , λ ≥ α . \theta_*\leq\lim\frac{g(n)}{F_{k-1}}=\lambda\varphi\theta_*,\qquad\lambda\geq\alpha. θ ∗ ≤ lim F k − 1 g ( n ) = λ φ θ ∗ , λ ≥ α .
Using (13) , we obtain
lim e ( n ) n = 1 − λ ( 1 + α + L ) ≤ 1 − α ( ϕ + L ) = − α L . \lim\frac{e(n)}{n} = 1-\lambda(1+\alpha+L) \le1-\alpha(\phi+L)=-\alpha L. lim n e ( n ) = 1 − λ ( 1 + α + L ) ≤ 1 − α ( ϕ + L ) = − α L .
This proves (15) .
The cap gives C ( x ) ≤ min ( F j − 1 + x − F j , F j ) C(x)\le\min(F_{j-1}+x-F_j,F_j) C ( x ) ≤ min ( F j − 1 + x − F j , F j ) on [ F j , F j + 1 ) [F_j,F_{j+1}) [ F j , F j + 1 ) . Writing x = F j + q F j − 1 x=F_j+qF_{j-1} x = F j + q F j − 1 and using the Fibonacci ratios, it gives, uniformly in q ∈ [ 0 , 1 ] q\in[0,1] q ∈ [ 0 , 1 ] ,
d ( x ) ≤ H ( q ) + o ( 1 ) , H ( q ) = min ( α 3 q , α 2 ( 1 − q ) ) 1 + α q . (17) d(x)\le H(q)+o(1),\qquad H(q)=\frac{\min(\alpha^3q,\alpha^2(1-q))}{1+\alpha q}. \tag*{(17)} d ( x ) ≤ H ( q ) + o ( 1 ) , H ( q ) = 1 + α q min ( α 3 q , α 2 ( 1 − q )) . (17)
Since H H H is continuous and vanishes at both endpoints, d ( g ( n ) ) → L > 0 d(g(n))\to L>0 d ( g ( n )) → L > 0 forces q ( g ( n ) ) ∈ [ δ , 1 − δ ] q(g(n))\in[\delta,1-\delta] q ( g ( n )) ∈ [ δ , 1 − δ ] eventually for some fixed δ > 0 \delta>0 δ > 0 . The same subsequence thus proves E − ( δ ) ≥ α L E_-(\delta)\ge\alpha L E − ( δ ) ≥ α L . Condition (3) consequently forces L = 0 L=0 L = 0 , and the golden lower bound gives (1).
To prove (1) implies (2), let u , v u,v u , v be the minimum and maximum over all cycle points of T n T_n T n . Each has a cycle predecessor. Cycle capture keeps their arguments at a positive fraction of n n n . If (1) holds, then, for any small ε > 0 \varepsilon>0 ε > 0 and all large n n n , all these arguments obey m x ≤ C ( x ) ≤ r x mx\le C(x)\le rx m x ≤ C ( x ) ≤ r x , where m = α − ε m=\alpha-\varepsilon m = α − ε and r = α + ε < 1 r=\alpha+\varepsilon<1 r = α + ε < 1 . Taking predecessors gives
u ≥ n − r v , v ≤ n − m u , v − u ≤ r − m 1 − m r n . u\ge n-rv,\qquad v\le n-mu,\qquad v-u\le\frac{r-m}{1-mr}n. u ≥ n − r v , v ≤ n − m u , v − u ≤ 1 − m r r − m n .
Letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 shows that every cycle has width o ( n ) o(n) o ( n ) , including every selected step. Therefore e − ( n ) = o ( n ) e_-(n)=o(n) e − ( n ) = o ( n ) . Finally, (2) immediately implies (3).
The phase minimum selects an extremal child with a macroscopic negative jump. The cap then keeps that child away from both Fibonacci endpoints. Thus it remains to estimate negative jumps in each fixed interior interval.
Corollary 14. For any fixed 0 < δ ≤ α 2 0<\delta\le\alpha^2 0 < δ ≤ α 2 ,
L ≤ max { ϕ E − ( δ ) , α 3 δ 1 − α 2 δ } . L\le\max\left\{\phi E_-(\delta),\frac{\alpha^3\delta}{1-\alpha^2\delta}\right\}. L ≤ max { ϕ E − ( δ ) , 1 − α 2 δ α 3 δ } .
Proof. On the two boundary strips [ 0 , δ ] ∪ [ 1 − δ , 1 ] [0,\delta]\cup[1-\delta,1] [ 0 , δ ] ∪ [ 1 − δ , 1 ] , the maximum of H H H in (17) is α 3 δ / ( 1 − α 2 δ ) \alpha^3\delta/(1-\alpha^2\delta) α 3 δ / ( 1 − α 2 δ ) . If L L L exceeds this number, the extremal child subsequence must lie in the chosen interior, giving L ≤ ϕ E − ( δ ) L\le\phi E_-(\delta) L ≤ ϕ E − ( δ ) . Otherwise the second bound applies. □
Exact computation through 2 28 2^{28} 2 28 gives the maximum of e ( n ) / n e(n)/n e ( n ) / n on each dyadic shell [ 2 m , 2 m + 1 ) [2^m,2^{m+1}) [ 2 m , 2 m + 1 ) . On [ 2 27 , 2 28 ) [2^{27},2^{28}) [ 2 27 , 2 28 ) it is 653668 / 166238801 ≈ 0.003932102 653668/166238801 \approx0.003932102 653668/166238801 ≈ 0.003932102 , attained at n = 166238801 n=166238801 n = 166238801 with g = 102990319 g=102990319 g = 102990319 and T n ( g ) = 102336651 T_n(g)=102336651 T n ( g ) = 102336651 , and on [ 2 23 , 2 24 ) [2^{23},2^{24}) [ 2 23 , 2 24 ) it is 45807 / 9274448 ≈ 0.004939054 45807/9274448 \approx0.004939054 45807/9274448 ≈ 0.004939054 . The shell maxima are not monotone before 2 21 2^{21} 2 21 and decrease slowly from there on. From 2 21 2^{21} 2 21 on, each of them is attained on a two-cycle just to the right of a Fibonacci number. These finite data support investigation of the criterion but do not bound its limiting limsup.
A maximum principle and entropy budgets
We retain the canonical split g ( n ) = T n C ( n − 1 ) ( n − 1 ) g(n)=T_n^{C(n-1)}(n-1) g ( n ) = T n C ( n − 1 ) ( n − 1 ) and write
d ( n ) = C ( n ) / n − α , e ( n ) = n − g ( n ) − C ( g ( n ) ) , L = lim sup d ( n ) . d(n)=C(n)/n-\alpha,\qquad e(n)=n-g(n)-C(g(n)),\qquad L=\limsup d(n). d ( n ) = C ( n ) / n − α , e ( n ) = n − g ( n ) − C ( g ( n )) , L = lim sup d ( n ) .
All child labels below are inherited from closed Fibonacci blocks. The comparison and capture results established earlier are used throughout this section.
Proposition 16 (Maximum principle). For j ≥ 8 j\ge8 j ≥ 8 ,
sup n ≥ F j C ( n ) n = max F j ≤ n < F j + 2 C ( n ) n . (18) \sup_{n\ge F_j}\frac{C(n)}{n}=\max_{F_j\le n<F_{j+2}}\frac{C(n)}{n}. \tag*{(18)} n ≥ F j sup n C ( n ) = F j ≤ n < F j + 2 max n C ( n ) . (18)
Proof. For n ≥ F j + 2 ≥ F 10 = 55 n\ge F_{j+2}\ge F_{10}=55 n ≥ F j + 2 ≥ F 10 = 55 , Lemma 3 and capture put both selected children in [ F j , n ) [F_j,n) [ F j , n ) . Their ratios average to the parent ratio with weights g ( n ) / n g(n)/n g ( n ) / n and ( n − g ( n ) ) / n (n-g(n))/n ( n − g ( n )) / n . Strong induction therefore extends the finite maximum to the whole tail.
An exact computation through F 45 F_{45} F 45 gives the finite certificate
561724478 C ( n ) ≤ 367631381 n ( F 43 ≤ n < F 45 ) , 561724478C(n)\le367631381n\qquad(F_{43}\le n<F_{45}), 561724478 C ( n ) ≤ 367631381 n ( F 43 ≤ n < F 45 ) ,
with equality only at n = 561724478 n=561724478 n = 561724478 . The accompanying code contains a hash-table evaluator, a separate array checker and an independent Brent evaluator. The latter regenerated the full prefix through F 45 F_{45} F 45 from the initial values and confirmed the inequality and unique equality on all 701408733 indices of [ F 43 , F 45 ) [F_{43},F_{45}) [ F 43 , F 45 ) by integer cross products. The two evaluators give identical maxima on every complete Fibonacci block from order 20 through 44. Thus the same inequality holds for every n ≥ F 43 n\ge F_{43} n ≥ F 43 , and
lim sup C ( n ) / n ≤ 367631381 / 561724478 < 0.65446923. \limsup C(n)/n\le367631381/561724478<0.65446923. lim sup C ( n ) / n ≤ 367631381/561724478 < 0.65446923.
The finite verification is a computational premise. Its extension to an infinite tail is (18) .
For 0 ≤ t ≤ F k − 1 0\le t\le F_{k-1} 0 ≤ t ≤ F k − 1 , define
E k ( t ) = − D k ( t ) = F k − 1 + t − C ( F k + t ) , q = t / F k − 1 . E_k(t)=-D_k(t)=F_{k-1}+t-C(F_k+t),\qquad q=t/F_{k-1}. E k ( t ) = − D k ( t ) = F k − 1 + t − C ( F k + t ) , q = t / F k − 1 .
As before, E k = − D k E_k=-D_k E k = − D k is the nonnegative profile defect and e ( n ) e(n) e ( n ) is the selected orbit jump. Let f k f_k f k interpolate the grid values E k ( t ) / F k − 1 E_k(t)/F_{k-1} E k ( t ) / F k − 1 , and for j ≥ 8 j\geq8 j ≥ 8 let Ψ j \Psi_j Ψ j be the greatest common convex minorant of f j , f j + 1 f_j,f_{j+1} f j , f j + 1 . If F k + t ≥ 47 F_k+t\geq47 F k + t ≥ 47 and g ( F k + t ) = F k − 1 + s g(F_k+t)=F_{k-1}+s g ( F k + t ) = F k − 1 + s , Theorem 10 and the child localization (36) give
E k ( t ) = E k − 1 ( s ) + E k − 2 ( t − s ) , 0 ≤ s ≤ F k − 2 , 0 ≤ t − s ≤ F k − 3 . E_k(t)=E_{k-1}(s)+E_{k-2}(t-s),\qquad0\leq s\leq F_{k-2},\quad0\leq t-s\leq F_{k-3}. E k ( t ) = E k − 1 ( s ) + E k − 2 ( t − s ) , 0 ≤ s ≤ F k − 2 , 0 ≤ t − s ≤ F k − 3 .
Proposition 17 (Convex envelopes). The functions Ψ j \Psi_j Ψ j increase and converge uniformly to a continuous convex function Ψ ∞ \Psi_\infty Ψ ∞ satisfying
( q − α ) + ≤ Ψ ∞ ( q ) ≤ α 2 q , Ψ ∞ ( 0 ) = 0 , Ψ ∞ ( 1 ) = α 2 . (q-\alpha)_+\leq\Psi_\infty(q)\leq\alpha^2q,\qquad\Psi_\infty(0)=0,\qquad\Psi_\infty(1)=\alpha^2. ( q − α ) + ≤ Ψ ∞ ( q ) ≤ α 2 q , Ψ ∞ ( 0 ) = 0 , Ψ ∞ ( 1 ) = α 2 . Moreover,
L = max 0 ≤ q ≤ 1 α 2 q − Ψ ∞ ( q ) ϕ + q . (19) L=\max_{0\leq q\leq1}\frac{\alpha^2q-\Psi_\infty(q)}{\phi+q}. \tag*{(19)} L = 0 ≤ q ≤ 1 max ϕ + q α 2 q − Ψ ∞ ( q ) . (19) In particular, convergence of C ( n ) / n C(n)/n C ( n ) / n to α \alpha α is equivalent to Ψ ∞ ( q ) = α 2 q \Psi_\infty(q)=\alpha^2q Ψ ∞ ( q ) = α 2 q on [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Proof. Put a k = F k − 2 / F k − 1 a_k=F_{k-2}/F_{k-1} a k = F k − 2 / F k − 1 and b k = 1 − a k b_k=1-a_k b k = 1 − a k . The child phases q 0 = s / F k − 2 q_0=s/F_{k-2} q 0 = s / F k − 2 and q 1 = ( t − s ) / F k − 3 q_1=(t-s)/F_{k-3} q 1 = ( t − s ) / F k − 3 satisfy
q = a k q 0 + b k q 1 , f k ( q ) = a k f k − 1 ( q 0 ) + b k f k − 2 ( q 1 ) . q=a_kq_0+b_kq_1,\qquad f_k(q)=a_kf_{k-1}(q_0)+b_kf_{k-2}(q_1). q = a k q 0 + b k q 1 , f k ( q ) = a k f k − 1 ( q 0 ) + b k f k − 2 ( q 1 ) .
Jensen’s inequality propagates any common convex minorant of two successive profiles to every later profile. Thus Ψ j ≤ Ψ j + 1 \Psi_j\leq\Psi_{j+1} Ψ j ≤ Ψ j + 1 . The cap gives the common lower bound ( q − max { a j , a j + 1 } ) + (q-\max\{a_j,a_{j+1}\})_+ ( q − max { a j , a j + 1 } ) + . The endpoint values of Ψ j \Psi_j Ψ j are zero and min { F j − 3 / F j − 1 , F j − 2 / F j } < α 2 \min\{F_{j-3}/F_{j-1},F_{j-2}/F_j\}<\alpha^2 min { F j − 3 / F j − 1 , F j − 2 / F j } < α 2 , so convexity gives the upper bound. These bounds imply continuity of the limit at the endpoints. Convexity gives interior continuity, and monotone convergence on the compact interval is uniform.
For every real M M M , the affine function α 2 q − M ( ϕ + q ) \alpha^2q-M(\phi+q) α 2 q − M ( ϕ + q ) minorizes both f j , f j + 1 f_j,f_{j+1} f j , f j + 1 exactly when it minorizes Ψ j \Psi_j Ψ j . Hence the maximum of ( α 2 q − f k ( q ) ) / ( ϕ + q ) (\alpha^2q-f_k(q))/(\phi+q) ( α 2 q − f k ( q )) / ( ϕ + q ) over those two profiles equals the corresponding maximum with Ψ j \Psi_j Ψ j . A quotient of affine functions on an interpolation segment attains its maximum at an endpoint. At the grid points,
d ( F k + t ) = α 2 q − f k ( q ) + ( − 1 ) k α k / F k − 1 F k / F k − 1 + q . d(F_k+t)=\frac{\alpha^2q-f_k(q)+(-1)^k\alpha^k/F_{k-1}}{F_k/F_{k-1}+q}. d ( F k + t ) = F k / F k − 1 + q α 2 q − f k ( q ) + ( − 1 ) k α k / F k − 1 .
The discrepancy from the preceding quotient is uniform and tends to zero. The maximum principle and uniform envelope convergence prove (19) . □
The offset walk chooses the two children with probabilities σ = s / t \sigma=s/t σ = s / t and 1 − σ 1-\sigma 1 − σ when t > 0 t>0 t > 0 . A zero offset has zero probability. Put M = E k ( t ) / t M=E_k(t)/t M = E k ( t ) / t and λ = M / α 2 \lambda=M/\alpha^2 λ = M / α 2 . Both are martingales. A root is the starting node of this walk, with values q i n i t q_{\mathrm{init}} q init , M i n i t M_{\mathrm{init}} M init and λ i n i t \lambda_{\mathrm{init}} λ init . A stopping time is admissible if every active node before it has size at least 47. For a child of zero offset, assign its ratio M ( i ) M^{(i)} M ( i ) any value in [ 0 , 1 ] [0,1] [ 0 , 1 ] . With child ratios M ( 0 ) , M ( 1 ) M^{(0)},M^{(1)} M ( 0 ) , M ( 1 ) , define
K = KL ( ( σ , 1 − σ ) ∥ ( a k , b k ) ) , V = σ ( 1 − σ ) ( M ( 0 ) − M ( 1 ) ) 2 . K=\operatorname{KL}((\sigma,1-\sigma)\mathbin{\|}(a_k,b_k)),\qquad V=\sigma(1-\sigma)(M^{(0)}-M^{(1)})^2. K = KL (( σ , 1 − σ ) ∥ ( a k , b k )) , V = σ ( 1 − σ ) ( M ( 0 ) − M ( 1 ) ) 2 .
Proposition 18 (Offset entropy and a residual). For every bounded admissible stopping time T T T ,
E ∑ h < T K h = E log q T − log q i n i t ≤ log ( 1 / q i n i t ) , \mathbb{E}\sum_{h<T} K_h = \mathbb{E}\log q_T-\log q_{\mathrm{init}} \le\log(1/q_{\mathrm{init}}), E h < T ∑ K h = E log q T − log q init ≤ log ( 1/ q init ) , E ∑ h < T V h = E M T 2 − M i n i t 2 ≤ M i n i t ( 1 − M i n i t ) . \mathbb{E}\sum_{h<T} V_h = \mathbb{E}M_T^2-M_{\mathrm{init}}^2 \le M_{\mathrm{init}}(1-M_{\mathrm{init}}). E h < T ∑ V h = E M T 2 − M init 2 ≤ M init ( 1 − M init ) . The exact jump identity and the residual identity are
e ( F k + t ) = t − 2 s + E k − 1 ( s ) , e(F_k+t)=t-2s+E_{k-1}(s), e ( F k + t ) = t − 2 s + E k − 1 ( s ) , R = e / t + 2 a k − 1 − a k M R=e/t+2a_k-1-a_kM R = e / t + 2 a k − 1 − a k M = ( M − 2 ) ( σ − a k ) + σ ( 1 − σ ) ( M ( 0 ) − M ( 1 ) ) . =(M-2)(\sigma-a_k)+\sigma(1-\sigma)(M^{(0)}-M^{(1)}). = ( M − 2 ) ( σ − a k ) + σ ( 1 − σ ) ( M ( 0 ) − M ( 1 ) ) . They imply
R 2 ≤ 4 K + V / 2 , E ∑ h < T R h 2 ≤ 4 log ( 1 / q i n i t ) + M i n i t ( 1 − M i n i t ) / 2. R^2\le4K+V/2,\qquad\mathbb{E}\sum_{h<T}R_h^2\le4\log(1/q_{\mathrm{init}})+M_{\mathrm{init}}(1-M_{\mathrm{init}})/2. R 2 ≤ 4 K + V /2 , E h < T ∑ R h 2 ≤ 4 log ( 1/ q init ) + M init ( 1 − M init ) /2. Proof. The child phases are q σ / a k q\sigma/a_k q σ / a k and q ( 1 − σ ) / b k q(1-\sigma)/b_k q ( 1 − σ ) / b k . Conditioning gives the logarithmic drift K K K . The conditional variance of M M M is V V V . Telescoping and q ≤ 1 q\le1 q ≤ 1 , M 2 ≤ M M^2\le M M 2 ≤ M give the two budgets. The jump formula follows by substituting C ( g ) = F k − 2 + s − E k − 1 ( s ) C(g)=F_{k-2+s}-E_{k-1}(s) C ( g ) = F k − 2 + s − E k − 1 ( s ) in the definition of e e e . Subtracting the child average for M M M gives the residual identity. Since ∣ M − 2 ∣ ≤ 2 |M-2|\le2 ∣ M − 2∣ ≤ 2 and σ ( 1 − σ ) ≤ 1 / 4 \sigma(1-\sigma)\le1/4 σ ( 1 − σ ) ≤ 1/4 , R 2 ≤ 8 ( σ − a k ) 2 + V / 2 R^2\le8(\sigma-a_k)^2+V/2 R 2 ≤ 8 ( σ − a k ) 2 + V /2 . The second derivative of the binary divergence is 1 / ( z ( 1 − z ) ) ≥ 4 1/(z(1-z))\ge4 1/ ( z ( 1 − z )) ≥ 4 , giving K ≥ 2 ( σ − a k ) 2 K\ge2(\sigma-a_k)^2 K ≥ 2 ( σ − a k ) 2 .
These budgets constrain how a profile deficit can persist. Suppose roots at levels k i k_i k i satisfy q i n i t ≥ a > 0 q_{\mathrm{init}}\ge a>0 q init ≥ a > 0 and λ i n i t ≤ θ < 1 \lambda_{\mathrm{init}}\le\theta<1 λ init ≤ θ < 1 . Take H i → ∞ H_i\to\infty H i → ∞ with k i − 2 H i → ∞ k_i-2H_i\to\infty k i − 2 H i → ∞ , fix θ ′ ∈ ( θ , 1 ) \theta'\in(\theta,1) θ ′ ∈ ( θ , 1 ) , and put c = α 3 ( 1 − θ ′ ) / 2 c=\alpha^3(1-\theta')/2 c = α 3 ( 1 − θ ′ ) /2 . For every b ∈ ( 0 , 1 ) b\in(0,1) b ∈ ( 0 , 1 ) ,
lim inf i 1 H i ∑ h < H i P { q h ≥ b , e ( x h ) ≤ − c t h } ≥ 1 − θ θ ′ − log ( 1 / a ) log ( 1 / b ) . (20) \liminf_i\frac{1}{H_i}\sum_{h<H_i}\mathbb{P}\{q_h\ge b,\ e(x_h)\le-ct_h\}\ge1-\frac{\theta}{\theta'}-\frac{\log(1/a)}{\log(1/b)}. \tag*{(20)} i lim inf H i 1 h < H i ∑ P { q h ≥ b , e ( x h ) ≤ − c t h } ≥ 1 − θ ′ θ − log ( 1/ b ) log ( 1/ a ) . (20)
Indeed, Markov’s inequality controls the events λ h > θ ′ \lambda_h>\theta' λ h > θ ′ and q h < b q_h<b q h < b . The residual budget makes R h R_h R h tend to zero in Cesàro probability, while uniformly on these trees
R h = e ( x h ) / t h + α 3 ( 1 − λ h ) + o ( 1 ) . R_h=e(x_h)/t_h+\alpha^3(1-\lambda_h)+o(1). R h = e ( x h ) / t h + α 3 ( 1 − λ h ) + o ( 1 ) .
The claimed negative jump follows on the remaining mass. Both endpoints of that jump lie on the selected cycle, so its diameter is at least c t h ct_h c t h . This includes every cycle period.
For completeness, on the grid q = t / F k − 1 q=t/F_{k-1} q = t / F k − 1 with 1 ≤ t ≤ F k − 1 1\le t\le F_{k-1} 1 ≤ t ≤ F k − 1 , let B k ( θ ) B_k(\theta) B k ( θ ) be the largest coordinate with E k ( t ) / ( α 2 t ) ≤ θ E_k(t)/(\alpha^2t)\le\theta E k ( t ) / ( α 2 t ) ≤ θ , and let J k ( c ) J_k(c) J k ( c ) be the largest coordinate with e ( F k + t ) ≤ − c t e(F_k+t)\le-ct e ( F k + t ) ≤ − c t . Both maxima are zero for an empty set. Theorem 13 and ∣ e ( F k + t ) ∣ ≤ t |e(F_k+t)|\le t ∣ e ( F k + t ) ∣ ≤ t give
C ( n ) / n → α ⟺ B k ( θ ) → 0 ( 0 < θ < 1 ) ⟺ J k ( c ) → 0 ( c > 0 ) . C(n)/n\to\alpha\quad\Longleftrightarrow\quad B_k(\theta)\to0\ (0<\theta<1)\quad\Longleftrightarrow\quad J_k(c)\to0\ (c>0). C ( n ) / n → α ⟺ B k ( θ ) → 0 ( 0 < θ < 1 ) ⟺ J k ( c ) → 0 ( c > 0 ) .
For the first equivalence, use the exact formula for d ( F k + t ) d(F_k+t) d ( F k + t ) above away from q = 0 q=0 q = 0 and the cap near q = 0 q=0 q = 0 . For the second, convergence forces all cycle diameters to be o ( n ) o(n) o ( n ) . Conversely, if J k ( c ) → 0 J_k(c)\to0 J k ( c ) → 0 , then either e − ( n ) < c t e_-(n)<ct e − ( n ) < c t or e − ( n ) / n ≤ t / n ≤ J k ( c ) e_-(n)/n\le t/n\le J_k(c) e − ( n ) / n ≤ t / n ≤ J k ( c ) . At t = 0 t=0 t = 0 , the Fibonacci landing statement of Theorem 7 gives e ( F k ) = 0 e(F_k)=0 e ( F k ) = 0 for every k ≥ 6 k\ge6 k ≥ 6 . Letting c c c tend to zero proves e − ( n ) = o ( n ) e_-(n)=o(n) e − ( n ) = o ( n ) , and Theorem 13 applies. The convergence assertion remains a conjecture.
Martingales and the dispersion route
Use labelled states ( j , N ) (j,N) ( j , N ) with F j ≤ N ≤ F j + 1 F_j\le N\le F_{j+1} F j ≤ N ≤ F j + 1 , and let the selected split be N = a + b N=a+b N = a + b with inherited child labels j − 1 j-1 j − 1 , j − 2 j-2 j − 2 . Retain these labels at Fibonacci endpoints rather than recomputing a canonical order. Choose the first child with probability a / N a/N a / N and the second with probability b / N b/N b / N . Define
Z ( N ) = C ( N ) − α N N , X ( j , N ) = F j N . Z(N)=\frac{C(N)-\alpha N}{N}, \qquad X(j,N)=\frac{F_j}{N}. Z ( N ) = N C ( N ) − α N , X ( j , N ) = N F j .
Proposition 19 (Exact martingales and local variance). Both Z Z Z and X X X are martingales for this size-biased child choice. If A = F j − 1 A=F_{j-1} A = F j − 1 and B = F j − 2 B=F_{j-2} B = F j − 2 , the one-step conditional variance of X X X is
v ( j , N ) = ( A b − B a ) 2 N 2 a b . (21) v(j,N)=\frac{(Ab-Ba)^2}{N^2ab}. \tag*{(21)} v ( j , N ) = N 2 ab ( A b − B a ) 2 . (21) Writing V 0 = 0 V_0=0 V 0 = 0 , the accumulated variance satisfies
V m ( j , N ) = v ( j , N ) + a N V m − 1 ( j − 1 , a ) + b N V m − 1 ( j − 2 , b ) , (22) V_m(j,N)=v(j,N)+\frac{a}{N}V_{m-1}(j-1,a)+\frac{b}{N}V_{m-1}(j-2,b), \tag*{(22)} V m ( j , N ) = v ( j , N ) + N a V m − 1 ( j − 1 , a ) + N b V m − 1 ( j − 2 , b ) , (22) with terminal orders stopped at 4 or 5.
Proof. The martingale identities follow from C ( N ) = C ( a ) + C ( b ) C(N)=C(a)+C(b) C ( N ) = C ( a ) + C ( b ) and F j = F j − 1 + F j − 2 F_j=F_{j-1}+F_{j-2} F j = F j − 1 + F j − 2 . Subtracting the weighted mean of the two child values of X X X gives (21) , and conditioning on the first child choice gives (22) .
Theorem 20 (Conditional quartic decay). Assume that there are κ > 0 \kappa>0 κ > 0 and J J J such that every labelled state ( j , N ) (j,N) ( j , N ) reached by the selected splits satisfies
V 4 ( j , N ) ≥ κ ( C ( N ) − G ( N ) N ) 4 , j ≥ J . (23) V_4(j,N)\ge\kappa\left(\frac{C(N)-G(N)}{N}\right)^4,\qquad j\ge J. \tag*{(23)} V 4 ( j , N ) ≥ κ ( N C ( N ) − G ( N ) ) 4 , j ≥ J . (23) Then
C ( n ) − α n = O ( n ( log n ) 1 / 4 ) . (24) C(n)-\alpha n=O\left(\frac{n}{(\log n)^{1/4}}\right). \tag*{(24)} C ( n ) − α n = O ( ( log n ) 1/4 n ) . (24)
Proof. Let z = Z ( N ) z=Z(N) z = Z ( N ) at a root of order j j j . All labelled values of X X X lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , so its total expected quadratic variation is at most 1. Take H = ⌊ ( j − max ( J , ⌊ j / 2 ⌋ ) ) / 8 ⌋ H=\lfloor(j-\max(J,\lfloor j/2\rfloor))/8\rfloor H = ⌊( j − max ( J , ⌊ j /2 ⌋)) /8 ⌋ disjoint four-generation blocks. Each child step lowers order by at most two, so all nodes in these blocks have order at least max ( J , ⌊ j / 2 ⌋ ) \max(J,\lfloor j/2\rfloor) max ( J , ⌊ j /2 ⌋) . The difference between ( C ( m ) − G ( m ) ) / m (C(m)-G(m))/m ( C ( m ) − G ( m )) / m and Z ( m ) Z(m) Z ( m ) is at most 1 / m 1/m 1/ m . Write ε j = 1 / F ⌊ j / 2 ⌋ \varepsilon_j=1/F_{\lfloor j/2\rfloor} ε j = 1/ F ⌊ j /2 ⌋ . At each block start the martingale identity and Jensen’s inequality give
E [ ( C ( m ) − G ( m ) m ) 4 ] ≥ ( ( z − ε j ) + ) 4 . \mathbb{E}\left[\left(\frac{C(m)-G(m)}{m}\right)^4\right]\geq((z-\varepsilon_j)_+)^4. E [ ( m C ( m ) − G ( m ) ) 4 ] ≥ (( z − ε j ) + ) 4 .
Summing the assumed four-step variance bounds yields 1 ≥ H κ ( ( z − ε j ) + ) 4 1\geq H\kappa((z-\varepsilon_j)_+)^4 1 ≥ H κ (( z − ε j ) + ) 4 . As H ≍ j H\asymp j H ≍ j and the lower bound gives z ≥ − 1 / N z\geq-1/N z ≥ − 1/ N , ∣ z ∣ = O ( j − 1 / 4 ) |z|=O(j^{-1/4}) ∣ z ∣ = O ( j − 1/4 ) . Finally j ≍ log N j\asymp\log N j ≍ log N proves the result. □ \square □
Scalar iteration and inverse rays
The iteration x ↦ C ( x ) x\mapsto C(x) x ↦ C ( x ) provides a different view of the Fibonacci structure. It is distinct from the inner map T n T_n T n and from a path through the two-child recursion. The cap and lower bound imply
F k − 1 ≤ C ( x ) ≤ F k ( F k < x < F k + 1 ) . F_{k-1}\leq C(x)\leq F_k\qquad(F_k<x<F_{k+1}). F k − 1 ≤ C ( x ) ≤ F k ( F k < x < F k + 1 ) .
Consequently every preimage of a non-Fibonacci value in the open block ( F k , F k + 1 ) (F_k,F_{k+1}) ( F k , F k + 1 ) lies in the next open block.
Theorem 21. Let N ≥ F 43 N\geq F_{43} N ≥ F 43 and start at a non-Fibonacci integer x 0 > N x_0>N x 0 > N . Iterate x i + 1 = C ( x i ) x_{i+1}=C(x_i) x i + 1 = C ( x i ) , stopping at the first Fibonacci output or the first value at most N N N . For any prefix before this stop,
∑ i ( d ( x i ) ) + < 1 3 , ∑ i ∣ d ( x i ) ∣ < 1 3 + 2 N . \sum_i (d(x_i))_+<\frac{1}{3},\qquad\sum_i |d(x_i)|<\frac{1}{3}+\frac{2}{N}. i ∑ ( d ( x i ) ) + < 3 1 , i ∑ ∣ d ( x i ) ∣ < 3 1 + N 2 . where the sums run over the source indices in that prefix. Every strictly increasing infinite inverse ray C ( s j + 1 ) = s j C(s_{j+1})=s_j C ( s j + 1 ) = s j satisfies
∑ j ∣ d ( s j ) ∣ < ∞ , s j + 1 / s j ⟶ ϕ . \sum_j |d(s_j)|<\infty,\qquad s_{j+1}/s_j\longrightarrow\phi. j ∑ ∣ d ( s j ) ∣ < ∞ , s j + 1 / s j ⟶ ϕ . If the ray is eventually non-Fibonacci, write F h + j < s j < F h + j + 1 F_{h+j}<s_j<F_{h+j+1} F h + j < s j < F h + j + 1 after discarding a finite prefix. Then
5 ( s j + 1 ) α h + j ↓ λ ∈ [ 1 , ϕ ) , s j / F h + j ⟶ λ . \sqrt{5}(s_j+1)\alpha^{h+j}\downarrow\lambda\in[1,\phi),\qquad s_j/F_{h+j}\longrightarrow\lambda. 5 ( s j + 1 ) α h + j ↓ λ ∈ [ 1 , ϕ ) , s j / F h + j ⟶ λ .
Proof. The shifted ratio β ( x ) = ( C ( x ) + 1 ) / ( x + 1 ) \beta(x)=(C(x)+1)/(x+1) β ( x ) = ( C ( x ) + 1 ) / ( x + 1 ) is strictly greater than α \alpha α , by the golden floor bound. If x 0 x_0 x 0 is in open block k k k , all nonterminal steps lower the block order by one. Give the endpoint x r x_r x r the inherited closed block [ F p , F p + 1 ] [F_p,F_{p+1}] [ F p , F p + 1 ] , p = k − r p=k-r p = k − r . With Λ i = 5 ( x i + 1 ) α k − i \Lambda_i=\sqrt{5}(x_i+1)\alpha^{k-i} Λ i = 5 ( x i + 1 ) α k − i we have exactly
∑ i < r log β ( x i ) α = log Λ r Λ 0 . (25) \sum_{i<r}\log\frac{\beta(x_i)}{\alpha}=\log\frac{\Lambda_r}{\Lambda_0}. \tag*{(25)} i < r ∑ log α β ( x i ) = log Λ 0 Λ r . (25)
Binet’s formula gives Λ 0 > 1 \Lambda_0 > 1 Λ 0 > 1 . The last source exceeds N N N , so x r > α N − α 2 > N / 2 x_r > \alpha N - \alpha^2 > N/2 x r > α N − α 2 > N /2 . Also F p + 1 α p ≤ ϕ ( 1 + α 6 ) / 5 < 1 F_{p+1}\alpha^p \le\phi(1+\alpha^6)/\sqrt{5} < 1 F p + 1 α p ≤ ϕ ( 1 + α 6 ) / 5 < 1 for p ≥ 2 p \ge2 p ≥ 2 , whence α p < 1 / x r < 2 / N \alpha^p < 1/x_r < 2/N α p < 1/ x r < 2/ N . A second application of Binet gives
Λ r ≤ ϕ + 5 α p + ϕ α 2 p + 2 < ϕ + 7 / N . \Lambda_r \le\phi+\sqrt{5}\alpha^p+\phi\alpha^{2p+2}<\phi+7/N. Λ r ≤ ϕ + 5 α p + ϕ α 2 p + 2 < ϕ + 7/ N .
Thus the logarithmic sum is less than log ϕ + 7 / N \log\phi+7/N log ϕ + 7/ N . The tail bound in § 7 gives C ( x ) / x < 2 / 3 C(x)/x<2/3 C ( x ) / x < 2/3 at every source. Write ε = β − α \varepsilon=\beta-\alpha ε = β − α . Since log ( β / α ) ≥ ε / β \log(\beta/\alpha)\ge\varepsilon/\beta log ( β / α ) ≥ ε / β and ( d ( x ) ) + ≤ ( 1 + 1 / N ) ε (d(x))_+\le(1+1/N)\varepsilon ( d ( x ) ) + ≤ ( 1 + 1/ N ) ε ,
∑ i < r ( d ( x i ) ) + < ( 1 + 1 / N ) ( 2 3 + 1 3 N ) ( log ϕ + 7 / N ) < 1 3 . \sum_{i<r}(d(x_i))_+ < (1+1/N)\left(\frac{2}{3}+\frac{1}{3N}\right)(\log\phi+7/N)<\frac{1}{3}. i < r ∑ ( d ( x i ) ) + < ( 1 + 1/ N ) ( 3 2 + 3 N 1 ) ( log ϕ + 7/ N ) < 3 1 .
For the last inequality, log ϕ < 49 / 100 \log\phi<49/100 log ϕ < 49/100 and N ≥ F 43 N\ge F_{43} N ≥ F 43 suffice. The negative part is at most α 2 / x i \alpha^2/x_i α 2 / x i . Reverse geometric summation, using x i + 1 < 2 x i / 3 x_{i+1}<2x_i/3 x i + 1 < 2 x i /3 , gives ∑ i < r 1 / x i < 3 / N \sum_{i<r}1/x_i<3/N ∑ i < r 1/ x i < 3/ N . As 3 α 2 < 2 3\alpha^2<2 3 α 2 < 2 , this proves the absolute bound.
On an inverse ray, once a non-Fibonacci value occurs all later values are non-Fibonacci, and each edge advances one open block. Reverse a finite segment ending at a sufficiently large fixed s 0 s_0 s 0 and apply the preceding bound with N = s 0 N=s_0 N = s 0 . Monotone partial sums give absolute summability on the infinite ray. An eventual Fibonacci ray instead has s j = F h + j s_j=F_{h+j} s j = F h + j , and Binet gives the same conclusion directly. In either case d ( s j ) → 0 d(s_j)\to0 d ( s j ) → 0 and the inverse equation gives the ratio limit.
For a non-Fibonacci ray, put Λ j = 5 ( s j + 1 ) α h + j \Lambda_j=\sqrt{5}(s_j+1)\alpha^{h+j} Λ j = 5 ( s j + 1 ) α h + j . The inverse equation gives Λ j + 1 / Λ j = α / β ( s j + 1 ) < 1 \Lambda_{j+1}/\Lambda_j=\alpha/\beta(s_{j+1})<1 Λ j + 1 / Λ j = α / β ( s j + 1 ) < 1 , while Binet gives Λ j > 1 \Lambda_j>1 Λ j > 1 . At every odd block order p = h + j p=h+j p = h + j , the integer inequality s j + 1 ≤ F p + 1 s_j+1\le F_{p+1} s j + 1 ≤ F p + 1 gives Λ j ≤ ϕ ( 1 − α 2 p + 2 ) < ϕ \Lambda_j\le\phi(1-\alpha^{2p+2})<\phi Λ j ≤ ϕ ( 1 − α 2 p + 2 ) < ϕ . Its limit therefore belongs to [ 1 , ϕ ) [1,\phi) [ 1 , ϕ ) , and the claimed normalization follows from Binet.
For each fixed c > 0 c>0 c > 0 and each such ray, absolute summability also gives
∑ { j : d ( s j ) ≥ c / log s j } j − 1 / 2 < ∞ , # { j ≤ J : d ( s j ) ≥ c / log s j } = o ( J ) . \sum_{\{j:d(s_j)\ge c/\sqrt{\log s_j}\}}j^{-1/2}<\infty,\qquad
\#\{j\le J:d(s_j)\ge c/\sqrt{\log s_j}\}=o(\sqrt{J}). { j : d ( s j ) ≥ c / l o g s j } ∑ j − 1/2 < ∞ , # { j ≤ J : d ( s j ) ≥ c / log s j } = o ( J ) .
Indeed, log s j = j log ϕ + O ( 1 ) \log s_j=j\log\phi+O(1) log s j = j log ϕ + O ( 1 ) . It suffices to split the convergent weighted sum at a fixed index and then let that index tend to infinity. The theorem concerns every existing inverse ray. Existence from an arbitrary root and control of the two-child recursion require further arguments.
Grytczuk’s fixed-depth comparison
Grytczuk’s recurrence [5 ] , recorded as [A093878], is
A ( 1 ) = A ( 2 ) = 1 , A ( n ) = A ( A ( A ( n − 1 ) ) ) + A ( n − A ( A ( n − 1 ) ) ) ( n ≥ 3 ) . (26) A(1)=A(2)=1,\qquad A(n)=A(A(A(n-1)))+A(n-A(A(n-1)))\quad(n\ge3). \tag*{(26)} A ( 1 ) = A ( 2 ) = 1 , A ( n ) = A ( A ( A ( n − 1 ))) + A ( n − A ( A ( n − 1 ))) ( n ≥ 3 ) . (26)
It is the ( k , a , b ) = ( 2 , 0 , 1 ) (k,a,b)=(2,0,1) ( k , a , b ) = ( 2 , 0 , 1 ) case of the family
A ( n ) = A ( n − a − A k ( n − b ) ) + A ( A k ( n − b ) ) A(n)=A(n-a-A^k(n-b))+A(A^k(n-b)) A ( n ) = A ( n − a − A k ( n − b )) + A ( A k ( n − b ))
studied by Isgur and Rahman [6 ] , where A k A^k A k denotes k k k -fold composition. Their Proposition 1 establishes slow growth and unboundedness under initial conditions satisfied here, and their Theorem 2.1 proves generalized Fibonacci anchors. They credit Grytczuk with the binary-word interpretation and A ( F j ) = F j − 1 A(F_j)=F_{j-1} A ( F j ) = F j − 1 in this case, and explicitly leave convergence of A ( n ) / n A(n)/n A ( n ) / n open for k ≥ 2 k\ge2 k ≥ 2 . The theorem below settles the k = 2 k=2 k = 2 instance of that question and determines the sharp error order. It makes no assertion for k > 2 k>2 k > 2 .
We derive the required Pascal-word description in Appendix § 15 and use cancellation between a run and its neighboring Pascal word. The use of Pascal words itself is classical, and [7 Sections 1.1, 1.3 and Appendix B] constructs these blocks and relates them to the first differences of Conway’s sequence. Here the Fibonacci interval decomposition and the cancellation between its pieces give the following quantitative comparison for (26) .
Theorem 22. The sequence in (26) satisfies
A ( n ) = α n + O ( n log n ) . A(n)=\alpha n+O\left(\frac{n}{\sqrt{\log n}}\right). A ( n ) = α n + O ( log n n ) . Moreover,
max F m + 2 ≤ n ≤ F m + 3 ∣ A ( n ) − α n ∣ = Θ ( F m + 1 m ) . \max_{F_{m+2}\le n\le F_{m+3}} \lvert A(n)-\alpha n\rvert=\Theta\left(\frac{F_{m+1}}{\sqrt{m}}\right). F m + 2 ≤ n ≤ F m + 3 max ∣ A ( n ) − α n ∣ = Θ ( m F m + 1 ) . In particular, A ( n ) / n → α A(n)/n\to\alpha A ( n ) / n → α , and the global error is not o ( n / log n ) o(n/\sqrt{\log n}) o ( n / log n ) . The lower bound concerns interval maxima.
Proof. For r ≥ 1 r\ge1 r ≥ 1 , define Pascal words by W ( r , 0 ) = 0 W(r,0)=0 W ( r , 0 ) = 0 , W ( r , r ) = 1 W(r,r)=1 W ( r , r ) = 1 and W ( r , j ) = W ( r − 1 , j ) W ( r − 1 , j − 1 ) W(r,j)=W(r-1,j)W(r-1,j-1) W ( r , j ) = W ( r − 1 , j ) W ( r − 1 , j − 1 ) for 0 < j < r 0<j<r 0 < j < r . For m ≥ 2 m\ge2 m ≥ 2 , the first-difference word on ( F m + 2 , F m + 3 ] (F_{m+2},F_{m+3}] ( F m + 2 , F m + 3 ] is
S m = ∏ j = ⌊ ( m − 1 ) / 2 ⌋ 0 1 ( m − 2 − j j ) W ( m − 1 − j , j ) , (27) S_m=\prod_{j=\lfloor(m-1)/2\rfloor}^{0}1^{\binom{m-2-j}{j}}W(m-1-j,j), \tag*{(27)} S m = j = ⌊( m − 1 ) /2 ⌋ ∏ 0 1 ( j m − 2 − j ) W ( m − 1 − j , j ) , (27)
where the product is in decreasing j j j order. The initial endpoint is A ( F m + 2 ) = F m + 1 A(F_{m+2})=F_{m+1} A ( F m + 2 ) = F m + 1 . Appendix § 15 derives these identities.
Put l = m − 1 l=m-1 l = m − 1 , B j = ( l − j j ) B_j=\binom{l-j}{j} B j = ( j l − j ) and R j = ( l − j − 1 j ) R_j=\binom{l-j-1}{j} R j = ( j l − j − 1 ) . Each run/word pair has length R j + B j R_j+B_j R j + B j and B j B_j B j ones. Its excess over density α \alpha α is
e j = B j − α ( B j + R j ) = α B j ( α − d j ) , d j = R j B j = l − 2 j l − j . e_j=B_j-\alpha(B_j+R_j)=\alpha B_j(\alpha-d_j),\qquad d_j=\frac{R_j}{B_j}=\frac{l-2j}{l-j}. e j = B j − α ( B j + R j ) = α B j ( α − d j ) , d j = B j R j = l − j l − 2 j .
Give I = l − 2 j I=l-2j I = l − 2 j probability B j / F l + 1 B_j/F_{l+1} B j / F l + 1 . The polynomial
P l ( u ) = ∑ j B j u l − 2 j = r ( u ) l + 1 − s ( u ) l + 1 u 2 + 4 , r ( u ) , s ( u ) = u ± u 2 + 4 2 P_l(u)=\sum_j B_j u^{l-2j}=\frac{r(u)^{l+1}-s(u)^{l+1}}{\sqrt{u^2+4}},\qquad r(u),s(u)=\frac{u\pm\sqrt{u^2+4}}{2} P l ( u ) = j ∑ B j u l − 2 j = u 2 + 4 r ( u ) l + 1 − s ( u ) l + 1 , r ( u ) , s ( u ) = 2 u ± u 2 + 4
satisfies P l = u P l − 1 + P l − 2 P_l = uP_{l-1} + P_{l-2} P l = u P l − 1 + P l − 2 . Differentiating log P l ( e t ) \log P_l(e^t) log P l ( e t ) twice at zero gives E I = l / 5 + O ( 1 ) \mathbb{E}I = l/\sqrt{5} + O(1) E I = l / 5 + O ( 1 ) and Var I = 4 l / ( 5 5 ) + O ( 1 ) \operatorname{Var} I = 4l/(5\sqrt{5}) + O(1) Var I = 4 l / ( 5 5 ) + O ( 1 ) . The function h ( x ) = 2 x / ( 1 + x ) h(x) = 2x/(1 + x) h ( x ) = 2 x / ( 1 + x ) obeys h ( 1 / 5 ) = α h(1/\sqrt{5}) = \alpha h ( 1/ 5 ) = α and ∣ h ′ ∣ ≤ 2 |h'| \le2 ∣ h ′ ∣ ≤ 2 on [ 0 , 1 ] [0,1] [ 0 , 1 ] , while d j = h ( I / l ) d_j = h(I/l) d j = h ( I / l ) . Cauchy–Schwarz therefore yields
∑ j ∣ e j ∣ = O ( F m / m ) . \sum_j |e_j| = O(F_m/\sqrt{m}). j ∑ ∣ e j ∣ = O ( F m / m ) .
This bounds the discrepancy at every complete-pair boundary.
For an unfinished pair, put p = α 2 p = \alpha^2 p = α 2 and t = l − j t = l-j t = l − j . The identity
( t j ) p j ( 1 − p ) t − j = α l B j \binom{t}{j}p^j(1-p)^{t-j} = \alpha^l B_j ( j t ) p j ( 1 − p ) t − j = α l B j
and the standard binomial point-probability bound give max j B j = O ( F m / m ) \max_j B_j = O(F_m/\sqrt{m}) max j B j = O ( F m / m ) , since t ≥ l / 2 t \ge l/2 t ≥ l /2 . Each pair has length at most 2 B j 2B_j 2 B j , so the same estimate holds for every prefix. The starting error satisfies
F m + 1 − α F m + 2 = ( − 1 ) m + 2 α m + 2 . F_{m+1} - \alpha F_{m+2} = (-1)^{m+2}\alpha^{m+2}. F m + 1 − α F m + 2 = ( − 1 ) m + 2 α m + 2 .
Since n ≍ F m + 1 n \asymp F_{m+1} n ≍ F m + 1 and m ≍ log n m \asymp\log n m ≍ log n , the upper bound follows.
For the lower bound choose a central index with l − 2 j = l / 5 + O ( 1 ) l - 2j = l/\sqrt{5} + O(1) l − 2 j = l / 5 + O ( 1 ) on the admissible parity lattice. Stirling’s formula gives B j ≍ F m / m B_j \asymp F_m/\sqrt{m} B j ≍ F m / m , and R j / B j → α R_j/B_j \to\alpha R j / B j → α . The all-one run of length R j R_j R j changes A ( n ) − α n A(n) - \alpha n A ( n ) − α n by α 2 R j \alpha^2R_j α 2 R j . At least one of its two endpoints has absolute error at least α 2 R j / 2 \alpha^2R_j/2 α 2 R j /2 . This gives the matching interval lower bound.
Discussion and open problems
The two variable-depth examples have different asymptotic behavior. The Campbell orbit is compressed by a ternary scale and is completely classified. The Cloitre recurrence has a golden Fibonacci skeleton. Exact equality points, captured collars and the additive profile identity (10) persist across scales, while positive defects create nontrivial local cycles such as the five-cycle at 196.
The remaining convergence question is
lim n → ∞ C ( n ) n ? = α . \lim_{n\to\infty} \frac{C(n)}{n} \mathrel{?}= \alpha. n → ∞ lim n C ( n ) ? = α .
The elementary comparison determines the exact equality set and implies convergence in every sublinear-width Fibonacci neighborhood. The maximum principle gives the sharper global tail bound, and the convex envelope records exactly the possible remaining normalized excess. To obtain the full limit, it suffices to prove sublinear negative selected jumps when the landing point lies in each fixed interior Fibonacci subinterval. The local criterion and the global negative-jump condition are equivalent for the actual sequence, and localization narrows the estimate to be proved. The uniform dispersion condition (23) is a separate route to a quantitative rate. The scalar inverse-ray theorem gives absolute summability along a different family of paths. Passing from those paths to the selected two-child recursion is an additional problem, since the scalar estimate alone does not control its dispersion.
Acknowledgments
We thank John M. Campbell for the original variable-depth example and the questions that initiated this investigation.
AI use
Apart from the variable-depth example of John Campbell, the ideas studied in this paper are due to the authors, starting with the application of this idea to Conway’s recurrence. The relations with the golden ratio were first observed in numerical experiments that Benoît Cloitre designed and ran with Claude Opus 5.5 (Anthropic). Claude was then used to explore proof strategies and to run further experiments and checks. ChatGPT (GPT-6 Astra, OpenAI) was used in the same way for the arguments of § 7 and Appendix § 17 . Haobo Ma and Wenlin Zhang used AI tools for search, double-checking and proofreading. These were OpenAI Codex (GPT-6 Astra and GPT-6.1 Sol) and ChatGPT (GPT-6 Pro). All statements, proofs and computations were checked by the authors, who take full responsibility for the content and the wording. AI tools also helped with the translation into English.
Code and data availability
The reproducibility package is available at https://github.com/the-omega-institute/nested-recurrences . It contains independent recurrence evaluators, exact checks of the Campbell orbit rows, and the finite landing-jump data. The accompanying source archive contains the programs used for the finite tail certificate, the small orbit tables, and the profile checks, with reproduction instructions. The elementary proof of the golden structure in Appendix § 16 needs only its displayed initial values. The finite computation for the numerical tail bound covers [ F 43 , F 45 ) [F_{43}, F_{45}) [ F 43 , F 45 ) . Replaying the small checks does not require a fresh run of the full prefix. The recorded certificate and independent evaluator are available as versioned verification sources in that repository.
Deriving the Pascal words from the recurrence
First A A A is slow-growing and unbounded. Indeed, if s n = A ( A ( n − 1 ) ) s_n = A(A(n - 1)) s n = A ( A ( n − 1 )) , induction gives s n − s n − 1 ∈ { 0 , 1 } s_n - s_{n-1} \in\{0,1\} s n − s n − 1 ∈ { 0 , 1 } . Subtracting successive recurrences gives an earlier first difference, at n − s n n - s_n n − s n if s n = s n − 1 s_n = s_{n-1} s n = s n − 1 , and at s n s_n s n otherwise. The indices are legal since A ( t ) ≤ t − 1 A(t) \le t - 1 A ( t ) ≤ t − 1 for t ≥ 2 t \ge2 t ≥ 2 , and the base is A ( 3 ) = 2 A(3) = 2 A ( 3 ) = 2 . Eventual constancy at M M M would give M = A ( A ( M ) ) + M M = A(A(M)) + M M = A ( A ( M )) + M , contradicting positivity.
Let T ( k ) T(k) T ( k ) be the last occurrence of k k k , with T ( 0 ) = 0 T(0) = 0 T ( 0 ) = 0 . Then
T ( 1 ) = 2 , T ( k ) = A ( k ) + T ( k − A ( A ( k ) ) ) ( k ≥ 2 ) . (28) T(1) = 2,\qquad T(k) = A(k) + T(k - A(A(k))) \qquad(k \ge2). \tag*{(28)} T ( 1 ) = 2 , T ( k ) = A ( k ) + T ( k − A ( A ( k ))) ( k ≥ 2 ) . (28)
The case k = 2 k = 2 k = 2 is direct. For k ≥ 3 k \ge3 k ≥ 3 , put b = A ( k ) b = A(k) b = A ( k ) , u = A ( b ) u = A(b) u = A ( b ) and s = b + T ( k − u ) s = b + T(k - u) s = b + T ( k − u ) . Induction and slow growth give s > T ( k − 1 ) s > T(k - 1) s > T ( k − 1 ) . If u u u stays fixed, the earlier endpoint argument advances, whereas an increase in u u u also increases b b b and gives s = T ( k − 1 ) + 1 s = T(k - 1) + 1 s = T ( k − 1 ) + 1 . At n = T ( k ) + 1 n = T(k) + 1 n = T ( k ) + 1 the recurrence gives A ( n − b ) = k + 1 − u A(n - b) = k + 1 - u A ( n − b ) = k + 1 − u , so T ( k ) ≥ s T(k) \ge s T ( k ) ≥ s . If T ( k ) > s T(k) > s T ( k ) > s , then A ( s ) = A ( s + 1 ) = k A(s) = A(s + 1) = k A ( s ) = A ( s + 1 ) = k , but the recurrence at s + 1 s + 1 s + 1 gives u + A ( T ( k − u ) + 1 ) = k + 1 u + A(T(k - u) + 1) = k + 1 u + A ( T ( k − u ) + 1 ) = k + 1 , a contradiction.
Write μ ( k ) = T ( k ) − T ( k − 1 ) \mu(k) = T(k) - T(k - 1) μ ( k ) = T ( k ) − T ( k − 1 ) . Subtracting (28) , for k ≥ 3 k \ge3 k ≥ 3 , gives
μ ( k ) = { 1 , Δ A ( A ( k ) ) = 1 , μ ( k − A ( A ( k ) ) ) + Δ A ( k ) , Δ A ( A ( k ) ) = 0. \mu(k) =
\begin{cases}
1, & \Delta A(A(k)) = 1,\\
\mu(k - A(A(k))) + \Delta A(k), & \Delta A(A(k)) = 0.
\end{cases} μ ( k ) = { 1 , μ ( k − A ( A ( k ))) + Δ A ( k ) , Δ A ( A ( k )) = 1 , Δ A ( A ( k )) = 0.
where Δ A ( k ) = A ( k ) − A ( k − 1 ) \Delta A(k) = A(k) - A(k - 1) Δ A ( k ) = A ( k ) − A ( k − 1 ) and Δ A ( A ( k ) ) = A ( A ( k ) ) − A ( A ( k − 1 ) ) \Delta A(A(k)) = A(A(k)) - A(A(k - 1)) Δ A ( A ( k )) = A ( A ( k )) − A ( A ( k − 1 )) . The initial frequencies are μ ( 1 ) = 2 \mu(1) = 2 μ ( 1 ) = 2 , μ ( 2 ) = 1 \mu(2) = 1 μ ( 2 ) = 1 .
Encode each one and its following zeros in W ( r , j ) W(r,j) W ( r , j ) by their combined length, obtaining a word V ( r , j ) V(r,j) V ( r , j ) of positive integers. Thus V ( 1 , 1 ) = [ 1 ] V(1,1) = [1] V ( 1 , 1 ) = [ 1 ] , V ( r , 1 ) = [ r ] V(r,1) = [r] V ( r , 1 ) = [ r ] , V ( r , r ) = [ 1 ] V(r,r) = [1] V ( r , r ) = [ 1 ] , and V V V obeys the same concatenation rule for 1 < j < r 1 < j < r 1 < j < r . Set
ν m = ( ∏ j = ⌊ ( m − 1 ) / 2 ⌋ 1 1 ( m − 2 − j j ) V ( m − 1 − j , j ) ) (29) \nu_m = \left(\prod_{j=\lfloor(m-1)/2\rfloor}^{1} 1^{\binom{m-2-j}{j}}V(m-1-j,j)\right) \tag*{(29)} ν m = j = ⌊( m − 1 ) /2 ⌋ ∏ 1 1 ( j m − 2 − j ) V ( m − 1 − j , j ) (29)
Out-of-range words are empty and out-of-range binomial coefficients are zero. Its gap encoding, replacing c c c by 10 c − 1 10^{c-1} 1 0 c − 1 , is exactly S m S_m S m . The word ν m \nu_m ν m has F m F_m F m entries and total sum F m + 1 F_{m+1} F m + 1 .
For r ≥ 2 r \ge2 r ≥ 2 and 1 ≤ j ≤ r 1 \le j \le r 1 ≤ j ≤ r , we use the following replacement identity. In W ( r − 1 , j − 1 ) W(r - 1,j - 1) W ( r − 1 , j − 1 ) replace each one by the integer one, and replace successive zeros by the successive entries of V ( r − 1 , j ) V(r - 1,j) V ( r − 1 , j ) increased by one. The result is V ( r , j ) V(r,j) V ( r , j ) . For j = 1 j = 1 j = 1 and j = r j = r j = r this follows from the edge words. Otherwise split the input into W ( r − 2 , j − 1 ) W ( r − 2 , j − 2 ) W(r - 2,j - 1)W(r - 2,j - 2) W ( r − 2 , j − 1 ) W ( r − 2 , j − 2 ) . Its first part has ( r − 3 j − 1 ) \binom{r-3}{j-1} ( j − 1 r − 3 ) zeros, precisely the number of entries of V ( r − 2 , j ) V(r - 2,j) V ( r − 2 , j ) . Splitting the supplied word as V ( r − 2 , j ) V ( r − 2 , j − 1 ) V(r - 2,j)V(r - 2,j - 1) V ( r − 2 , j ) V ( r − 2 , j − 1 ) and applying induction proves the assertion. The row-two cases are checked directly.
We now prove that the frequencies on ( F m + 1 , F m + 2 ] (F_{m+1}, F_{m+2}] ( F m + 1 , F m + 2 ] are ν m \nu_m ν m . The bases ν 2 = [ 2 ] \nu_2 = [2] ν 2 = [ 2 ] , ν 3 = [ 1 , 2 ] \nu_3 = [1, 2] ν 3 = [ 1 , 2 ] follow from A ( 1 ) , … , A ( 8 ) = 1 , 1 , 2 , 3 , 3 , 4 , 5 , 5 A(1), \ldots, A(8) = 1, 1, 2, 3, 3, 4, 5, 5 A ( 1 ) , … , A ( 8 ) = 1 , 1 , 2 , 3 , 3 , 4 , 5 , 5 . Assume the earlier intervals known. As k k k traverses the next interval, the bits Δ A ( k ) \Delta A(k) Δ A ( k ) traverse U = S m − 1 U = S_{m-1} U = S m − 1 , and at each one of U U U the bits Δ A ( A ( k ) ) \Delta A(A(k)) Δ A ( A ( k )) consume the next bit of Z = S m − 2 Z = S_{m-2} Z = S m − 2 . The index k − A ( A ( k ) ) k - A(A(k)) k − A ( A ( k )) starts at F m F_m F m , advances exactly when that consumed bit is zero, and ends at F m + 1 F_{m+1} F m + 1 . Thus the frequency recurrence consumes Q = ν m − 1 Q = \nu_{m-1} Q = ν m − 1 as follows. A zero of U U U copies the next Q Q Q entry. A one consumes a Z Z Z bit and outputs one without consuming Q Q Q if that bit is one, and the next Q Q Q entry plus one otherwise.
For each decreasing j ≥ 1 j \ge1 j ≥ 1 , put r = m − 1 − j r = m - 1 - j r = m − 1 − j . The aligned pieces are
U : W ( r − 1 , j ) 1 ( r − 1 j − 1 ) , Z : 1 ( r − 2 j − 1 ) W ( r − 1 , j − 1 ) , Q : 1 ( r − 2 j ) V ( r − 1 , j ) . \begin{aligned}
U &: W(r - 1,j)1^{\binom{r-1}{j-1}},\\
Z &: 1^{\binom{r-2}{j-1}}W(r - 1,j - 1),\\
Q &: 1^{\binom{r-2}{j}}V(r - 1,j).
\end{aligned} U Z Q : W ( r − 1 , j ) 1 ( j − 1 r − 1 ) , : 1 ( j − 1 r − 2 ) W ( r − 1 , j − 1 ) , : 1 ( j r − 2 ) V ( r − 1 , j ) .
The U U U grouping moves the next run after the current Pascal word. The first U U U part has ( r − 2 j ) \binom{r-2}{j} ( j r − 2 ) zeros and ( r − 2 j − 1 ) \binom{r-2}{j-1} ( j − 1 r − 2 ) ones. These consume the initial runs of Q Q Q and Z Z Z and output ( r − 1 j ) \binom{r-1}{j} ( j r − 1 ) ones. The remaining all-one U U U part applies the replacement identity to output V ( r , j ) V(r,j) V ( r , j ) . Empty pieces handle the top parity cases, and the final zero of U U U copies the final [2 ] of Q Q Q . This proves ν m \nu_m ν m . Taking sums gives T ( F m + 2 ) = F m + 3 T(F_{m+2}) = F_{m+3} T ( F m + 2 ) = F m + 3 and closes the induction. The gap encoding proves (27) and its endpoint values.
An elementary proof of the golden structure
We prove the lower bound, equality classification and cap simultaneously. The proof uses the twenty-four initial values displayed below, and no large computed prefix. Write ρ ( m ) = { α ( m + 1 ) } \rho(m) = \{\alpha(m+1)\} ρ ( m ) = { α ( m + 1 )} and Δ ( m ) = C ( m ) − G ( m ) \Delta(m) = C(m)-G(m) Δ ( m ) = C ( m ) − G ( m ) , reserving E k E_k E k for the Fibonacci profiles. For a + b = n a+b=n a + b = n ,
δ ( a , b ) = G ( a ) + G ( b ) − G ( n ) = − ⌊ ρ ( a ) + ρ ( b ) − α ⌋ ∈ { − 1 , 0 , 1 } , \delta(a,b) = G(a) + G(b) - G(n) = -\lfloor\rho(a) + \rho(b) - \alpha\rfloor\in\{-1,0,1\}, δ ( a , b ) = G ( a ) + G ( b ) − G ( n ) = − ⌊ ρ ( a ) + ρ ( b ) − α ⌋ ∈ { − 1 , 0 , 1 } ,
Δ ( n ) = Δ ( a ) + Δ ( b ) + δ ( a , b ) . (30) \Delta(n) = \Delta(a) + \Delta(b) + \delta(a,b). \tag*{(30)} Δ ( n ) = Δ ( a ) + Δ ( b ) + δ ( a , b ) . (30)
The three carry values 1 1 1 , 0 0 0 , − 1 -1 − 1 correspond to the intervals [ 0 , α ) [0,\alpha) [ 0 , α ) , [ α , 1 + α ) [\alpha,1+\alpha) [ α , 1 + α ) and [ 1 + α , 2 ) [1+\alpha,2) [ 1 + α , 2 ) for ρ ( a ) + ρ ( b ) \rho(a)+\rho(b) ρ ( a ) + ρ ( b ) .
Initial values and cyclic selection
The following table lists the complete starting orbits through n = 24 n=24 n = 24 . A semicolon separates the transient from the cycle, and ranks start at zero. Every transition u ↦ v u \mapsto v u ↦ v is the substitution C ( u ) = n − v C(u)=n-v C ( u ) = n − v using an already known value. The selected rank is τ + ( ( h − τ ) mod p ) \tau+ ((h-\tau) \mathbin{\operatorname{mod}} p) τ + (( h − τ ) mod p ) , where h = C ( n − 1 ) h=C(n-1) h = C ( n − 1 ) and p p p is the cycle length.
In particular h ≥ τ h \ge\tau h ≥ τ in every row. The comparisons are
Table 4 (PDF p. 23).
Here U ( 1 ) = 1 U(1)=1 U ( 1 ) = 1 . The bounds 21 / 34 < α < 34 / 55 21/34 < \alpha< 34/55 21/34 < α < 34/55 determine all floors in this table, since the two rational products have the same floor for every multiplier from 2 to 25. The equality indices are exactly Z ∩ [ 1 , 24 ] = { 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 , 11 , 12 , 13 , 14 , 21 , 22 , 24 } \mathbb{Z} \cap[1,24] = \{1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14, 21, 22, 24\} Z ∩ [ 1 , 24 ] = { 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 , 11 , 12 , 13 , 14 , 21 , 22 , 24 } .
Proof of Lemma 3. Assume the earlier terms are positive and C ( m ) ≤ m C(m) \le m C ( m ) ≤ m , with the strict bound C ( m ) ≤ m − 1 C(m) \le m-1 C ( m ) ≤ m − 1 for m ≥ 2 m \ge2 m ≥ 2 . Then T n T_n T n maps [ 1 , n − 1 ] [1,n-1] [ 1 , n − 1 ] into [ 2 , n − 1 ] [2,n-1] [ 2 , n − 1 ] , since its image at 1 is n − 1 n-1 n − 1 and its value at x ≥ 2 x \ge2 x ≥ 2 is at least n − x + 1 n-x+1 n − x + 1 . Thus the children are earlier indices, at least one exceeds 1, and their values sum to at most n − 1 n-1 n − 1 . Adding the inductive half-bounds gives C ( n ) ≥ ⌈ n / 2 ⌉ C(n) \ge\lceil n/2 \rceil C ( n ) ≥ ⌈ n /2 ⌉ .
The values through 5 initialize C ( n ) ≤ 3 n / 4 C(n) \le3n/4 C ( n ) ≤ 3 n /4 . For n ≥ 6 n \ge6 n ≥ 6 , the earlier upper bound gives x i ≥ ( n + 3 ) / 4 > 2 x_i \ge(n+3)/4 > 2 x i ≥ ( n + 3 ) /4 > 2 for i ≥ 1 i \ge1 i ≥ 1 . Since h ≥ 2 h \ge2 h ≥ 2 , both a = x h a=x_h a = x h and b = C ( x h − 1 ) b=C(x_{h-1}) b = C ( x h − 1 ) are at least 2, so the upper bounds add. The values through 9 initialize C ( n ) ≥ 3 n / 5 C(n) \ge3n/5 C ( n ) ≥ 3 n /5 . For n ≥ 10 n \ge10 n ≥ 10 we have a , x h − 1 ≥ 4 a,x_{h-1} \ge4 a , x h − 1 ≥ 4 and C ( y ) ≥ 3 C(y) \ge3 C ( y ) ≥ 3 for y ≥ 4 y \ge4 y ≥ 4 , so both children are at least 3 and the lower bounds add as well.
For n ≥ 6 n \ge6 n ≥ 6 these bounds successively give
x i ≥ n + 3 4 ( i ≥ 1 ) , x i ≤ 17 n − 9 20 ( i ≥ 2 ) , x i ≥ 29 n + 27 80 ( i ≥ 3 ) . x_i \ge\frac{n+3}{4}\ (i \ge1),\qquad x_i \le\frac{17n-9}{20}\ (i \ge2),\qquad x_i \ge\frac{29n+27}{80}\ (i \ge3). x i ≥ 4 n + 3 ( i ≥ 1 ) , x i ≤ 20 17 n − 9 ( i ≥ 2 ) , x i ≥ 80 29 n + 27 ( i ≥ 3 ) .
The integer interval containing the tail from x 3 x_3 x 3 has at most ( 39 n + 17 ) / 80 (39n+17)/80 ( 39 n + 17 ) /80 elements. Distinctness before the first repetition gives
τ ≤ 2 + 39 n + 17 80 = 39 n + 177 80 ≤ 3 ( n − 1 ) 5 ≤ h ( n ≥ 25 ) . \tau\le2+\frac{39n+17}{80}=\frac{39n+177}{80}\le\frac{3(n-1)}{5}\le h \qquad(n\ge25). τ ≤ 2 + 80 39 n + 17 = 80 39 n + 177 ≤ 5 3 ( n − 1 ) ≤ h ( n ≥ 25 ) .
The middle inequality is 9 n ≥ 225 9n\ge225 9 n ≥ 225 . Table 3 handles 3 ≤ n ≤ 24 3\le n\le24 3 ≤ n ≤ 24 , proving cyclic selection for every n ≥ 3 n\ge3 n ≥ 3 .
Table 3. The initial orbits for C C C .
Rotation arithmetic
The Fibonacci recurrence gives
α F j − F j − 1 = ( − 1 ) j − 1 α j . (31) \alpha F_j-F_{j-1}=(-1)^{j-1}\alpha^j. \tag*{(31)} α F j − F j − 1 = ( − 1 ) j − 1 α j . (31)
Hence, for j ≥ 3 j\ge3 j ≥ 3 ,
ρ ( F j ) = α + ( − 1 ) j − 1 α j , ρ ( F j + 1 ) = 2 α − 1 + ( − 1 ) j − 1 α j , ρ ( F j − 1 ) = α j ( j odd ) . \rho(F_j)=\alpha+(-1)^{j-1}\alpha^j,\qquad\rho(F_j+1)=2\alpha-1+(-1)^{j-1}\alpha^j,\qquad\rho(F_j-1)=\alpha^j\qquad(j\text{ odd}). ρ ( F j ) = α + ( − 1 ) j − 1 α j , ρ ( F j + 1 ) = 2 α − 1 + ( − 1 ) j − 1 α j , ρ ( F j − 1 ) = α j ( j odd ) .
At 11 , 24 , 25 , 59 11,24,25,59 11 , 24 , 25 , 59 the fractions are respectively 12 α − 7 12\alpha-7 12 α − 7 , 25 α − 15 25\alpha-15 25 α − 15 , 26 α − 16 26\alpha-16 26 α − 16 and 60 α − 37 60\alpha-37 60 α − 37 . Each lies in ( 0 , α ) (0,\alpha) ( 0 , α ) , as follows from 37 / 60 < α < 5 / 8 37/60<\alpha<5/8 37/60 < α < 5/8 . Consequently, if z ∈ Z z\in\mathbb{Z} z ∈ Z , z ≥ 8 z\ge8 z ≥ 8 , then ρ ( z ) > α \rho(z)>\alpha ρ ( z ) > α exactly when z = F k z=F_k z = F k with odd k ≥ 7 k\ge7 k ≥ 7 . Also ρ ( z ) ≤ α + α 7 \rho(z)\le\alpha+\alpha^7 ρ ( z ) ≤ α + α 7 , so two such zeros have ρ ( a ) + ρ ( b ) ≤ 2 α + 2 α 7 < 1 + α \rho(a)+\rho(b)\le2\alpha+2\alpha^7<1+\alpha ρ ( a ) + ρ ( b ) ≤ 2 α + 2 α 7 < 1 + α . Thus their carry is nonnegative.
Lemma 23. If k ≥ 5 k\ge5 k ≥ 5 is odd and 0 < t < F k + 2 0<t<F_{k+2} 0 < t < F k + 2 is an integer, then { α t } ≥ 1 − α k \{\alpha t\}\ge1-\alpha^k { α t } ≥ 1 − α k if and only if t = F k + 1 t=F_{k+1} t = F k + 1 .
Proof. First, for j ≥ 3 j\ge3 j ≥ 3 , 0 < t < F j 0<t<F_j 0 < t < F j and any integer s s s ,
∣ α t − s ∣ ≥ α j − 1 , (32) |\alpha t-s|\ge\alpha^{j-1}, \tag*{(32)} ∣ α t − s ∣ ≥ α j − 1 , (32) with equality only at ( t , s ) = ( F j − 1 , F j − 2 ) (t,s)=(F_{j-1},F_{j-2}) ( t , s ) = ( F j − 1 , F j − 2 ) . Cassini’s identity makes ( F j , F j − 1 ) (F_j,F_{j-1}) ( F j , F j − 1 ) and ( F j − 1 , F j − 2 ) (F_{j-1},F_{j-2}) ( F j − 1 , F j − 2 ) an integer basis. Write ( t , s ) (t,s) ( t , s ) as their linear combination with coefficients u , v u,v u , v . The error is α j − 1 ∣ u α − v ∣ \alpha^{j-1}|u\alpha-v| α j − 1 ∣ uα − v ∣ . If u ≥ 1 u\ge1 u ≥ 1 , the bound t < F j t<F_j t < F j forces v ≤ − 1 v\le-1 v ≤ − 1 , and if u ≤ − 1 u\le-1 u ≤ − 1 , positivity forces v ≥ 1 v\ge1 v ≥ 1 . Both give a factor greater than 1. If u = 0 u=0 u = 0 , v ≥ 1 v\ge1 v ≥ 1 and equality requires v = 1 v=1 v = 1 .
For t < F k + 1 t<F_{k+1} t < F k + 1 , apply (31) with s = ⌈ α t ⌉ s=\lceil\alpha t\rceil s = ⌈ α t ⌉ . The proposed fraction would force t = F k t=F_k t = F k , whose error has the wrong sign. At F k + 1 F_{k+1} F k + 1 the fraction is 1 − α k + 1 1-\alpha^{k+1} 1 − α k + 1 and qualifies. Finally let t = F k + 1 + w t=F_{k+1}+w t = F k + 1 + w , 0 < w < F k 0<w<F_k 0 < w < F k . The same bound gives α k − 1 ≤ { α w } ≤ 1 − α k − 1 \alpha^{k-1}\le\{\alpha w\}\le1-\alpha^{k-1} α k − 1 ≤ { α w } ≤ 1 − α k − 1 . Subtracting α k + 1 \alpha^{k+1} α k + 1 does not cross zero and gives a fraction strictly below 1 − α k 1-\alpha^k 1 − α k .
Capture under prefix hypotheses
Assume for now, for x < n x<n x < n , the three assertions
C ( x ) ≥ G ( x ) , C ( x ) = G ( x ) ⇒ x ∈ Z , C ( x ) ≤ U ( x ) . (33) C(x)\ge G(x),\qquad C(x)=G(x)\Rightarrow x\in Z,\qquad C(x)\le U(x). \tag*{(33)} C ( x ) ≥ G ( x ) , C ( x ) = G ( x ) ⇒ x ∈ Z , C ( x ) ≤ U ( x ) . (33)
The function U U U is nondecreasing with increments 0 or 1. For an anchor A = F k ≥ 5 A=F_k\geq5 A = F k ≥ 5 , B = F k − 1 B=F_{k-1} B = F k − 1 , the following cones hold at arguments x < n x<n x < n .
x < A ∣ B + x − A + 1 ≤ C ( x ) ≤ B x ≥ A ∣ B ≤ C ( x ) ≤ B + x − A . (34) \begin{aligned}
x<A\quad&\vert\quad B+x-A+1\leq C(x)\leq B\\
x\geq A\quad&\vert\quad B\leq C(x)\leq B+x-A. \tag*{(34)}
\end{aligned} x < A x ≥ A ∣ B + x − A + 1 ≤ C ( x ) ≤ B ∣ B ≤ C ( x ) ≤ B + x − A . (34)
The upper bounds follow from U U U and the lower bound on the second row follows from G G G . For the strict first bound write x = A − u x=A-u x = A − u . If u ≥ 2 u\geq2 u ≥ 2 , α ( A − u + 1 ) − ( B − u + 1 ) = α 2 ( u − 1 ) + ( − 1 ) k − 1 α k > 0 \alpha(A-u+1)-(B-u+1)=\alpha^2(u-1)+(-1)^{k-1}\alpha^k>0 α ( A − u + 1 ) − ( B − u + 1 ) = α 2 ( u − 1 ) + ( − 1 ) k − 1 α k > 0 . For u = 1 u=1 u = 1 and odd k k k , G ( A − 1 ) = B G(A-1)=B G ( A − 1 ) = B . For even k ≥ 6 k\geq6 k ≥ 6 , G ( A − 1 ) = B − 1 G(A-1)=B-1 G ( A − 1 ) = B − 1 , but A − 1 ∉ Z A-1\notin\mathbb{Z} A − 1 ∈ / Z (including the four exceptions), so the zero implication in ( P ) (P) ( P ) supplies the additional unit.
Let I I I be the closed interval with endpoints A , n − B A,n-B A , n − B , and write its endpoints as ℓ , h \ell,h ℓ , h . The cones make I I I invariant and give
T n ( ℓ − u ) ∈ [ ℓ , h + u − 1 ] , T n ( h + u ) ∈ [ ℓ − u , h ] ( u ≥ 1 ) T_n(\ell-u)\in[\ell,h+u-1],\qquad T_n(h+u)\in[\ell-u,h]\qquad(u\geq1) T n ( ℓ − u ) ∈ [ ℓ , h + u − 1 ] , T n ( h + u ) ∈ [ ℓ − u , h ] ( u ≥ 1 )
whenever the arguments belong to the domain. Thus the integer distance to I I I decreases in at most two steps until it is zero. This proof does not evaluate C ( A ) C(A) C ( A ) , so the anchor may equal n n n .
Write q = F j ≤ n < F j + 1 = q + p q=F_j\leq n<F_{j+1}=q+p q = F j ≤ n < F j + 1 = q + p , p = F j − 1 p=F_{j-1} p = F j − 1 , r = F j − 2 r=F_{j-2} r = F j − 2 . For n ≥ 8 n\geq8 n ≥ 8 , applying capture at q q q and p p p gives, for every cycle point,
max ( n − p , p ) = : ℓ ≤ x ≤ h : = min ( q , n − r ) . (35) \max(n-p,p)=:\ell\leq x\leq h:=\min(q,n-r). \tag*{(35)} max ( n − p , p ) =: ℓ ≤ x ≤ h := min ( q , n − r ) . (35)
Since selection is cyclic, the oriented children obey
p ≤ a = g ( n ) ≤ q , r ≤ b = n − a ≤ p . (36) p\leq a=g(n)\leq q,\qquad r\leq b=n-a\leq p. \tag*{(36)} p ≤ a = g ( n ) ≤ q , r ≤ b = n − a ≤ p . (36)
A cycle predecessor y y y of a a a satisfies C ( y ) = b C(y)=b C ( y ) = b . Moreover, every cycle point is at most n − G ( ℓ ) n-G(\ell) n − G ( ℓ ) . Put s = F j − 3 s=F_{j-3} s = F j − 3 , t = F j − 4 t=F_{j-4} t = F j − 4 . The two child caps are
C ( a ) ≤ min ( a − s , p ) , C ( b ) ≤ min ( b − t , r ) . (37) C(a)\leq\min(a-s,p),\qquad C(b)\leq\min(b-t,r). \tag*{(37)} C ( a ) ≤ min ( a − s , p ) , C ( b ) ≤ min ( b − t , r ) . (37)
Adding separately the affine and constant bounds proves C ( n ) ≤ min ( n − r , q ) = U ( n ) C(n)\leq\min(n-r,q)=U(n) C ( n ) ≤ min ( n − r , q ) = U ( n ) .
We strengthen the induction at the changes of slope K j = F j + F j − 2 K_j=F_j+F_{j-2} K j = F j + F j − 2 by requiring
C ( K j ) < U ( K j ) ( j ≥ 6 ) , C ( K j ± 1 ) < U ( K j ± 1 ) ( j ≥ 8 ) . (38) C(K_j)<U(K_j)\ (j\geq6),\qquad C(K_j\pm1)<U(K_j\pm1)\ (j\geq8). \tag*{(38)} C ( K j ) < U ( K j ) ( j ≥ 6 ) , C ( K j ± 1 ) < U ( K j ± 1 ) ( j ≥ 8 ) . (38)
These statements follow before the lower bound at the current index. Indeed, let A = K j − 1 = p + s A=K_{j-1}=p+s A = K j − 1 = p + s , B = K j − 2 = r + t B=K_{j-2}=r+t B = K j − 2 = r + t and n = K j + v n=K_j+v n = K j + v . Equality throughout (37) would force
Table 1 (PDF p. 25).
For v = 0 , 1 v=0,1 v = 0 , 1 both constant caps must be attained, and for v = − 1 v=-1 v = − 1 both affine caps must be attained. In each row both children would saturate their own caps. The seed is C ( K 6 ) = C ( 11 ) = 7 < 8 C(K_6)=C(11)=7<8 C ( K 6 ) = C ( 11 ) = 7 < 8 . For j ≥ 7 j\geq7 j ≥ 7 the central row contradicts the earlier strict center at K j − 1 K_{j-1} K j − 1 , and for j ≥ 8 j\geq8 j ≥ 8 each neighbor row forces a strict center of order j − 1 j-1 j − 1 or j − 2 j-2 j − 2 to saturate. This proves the simultaneous propagation of (36).
The simultaneous induction
The initial table proves ( P ) (\mathcal{P}) ( P ) through 24 and initializes (38) . At n ≥ 25 n \ge25 n ≥ 25 assume both statements at all earlier indices. The preceding arguments establish the cap and any strict-knee assertion at n n n . We prove Δ ( n ) ≥ 0 \Delta(n) \ge0 Δ ( n ) ≥ 0 and its zero implication. In its Fibonacci block, j ≥ 8 j \ge8 j ≥ 8 , p ≥ 13 p \ge13 p ≥ 13 , r ≥ 8 r \ge8 r ≥ 8 .
If both child defects are positive, (29) gives Δ ( n ) ≥ 1 \Delta(n) \ge1 Δ ( n ) ≥ 1 . If exactly one is zero, the parent defect is nonnegative and can vanish only with carry − 1 -1 − 1 . Write z z z for the zero argument and w w w for the other. Then ρ ( z ) > α \rho(z) > \alpha ρ ( z ) > α , so z = F k z = F_k z = F k for odd k ≥ 7 k \ge7 k ≥ 7 , and { α ( w + 1 ) } ≥ 1 − α k \{\alpha(w+1)\} \ge1-\alpha^k { α ( w + 1 )} ≥ 1 − α k . If z = a z=a z = a , then b < a b<a b < a , and Lemma 23 excludes b + 1 ≤ F k b+1 \le F_k b + 1 ≤ F k . If z = b = p = F k z=b=p=F_k z = b = p = F k , the lemma forces a + 1 = q = F k + 1 a+1=q=F_{k+1} a + 1 = q = F k + 1 , whence n = F k + 2 − 1 ∈ Z n=F_{k+2}-1 \in\mathbb{Z} n = F k + 2 − 1 ∈ Z . If z = b = r = F k z=b=r=F_k z = b = r = F k , then a + 1 ∈ [ F k + 1 + 1 , F k + 2 + 1 ] a+1 \in[F_{k+1}+1,F_{k+2}+1] a + 1 ∈ [ F k + 1 + 1 , F k + 2 + 1 ] . The lemma excludes the interior below F k + 2 F_{k+2} F k + 2 , and the last two fractions are α k + 2 \alpha^{k+2} α k + 2 and α + α k + 2 \alpha+\alpha^{k+2} α + α k + 2 , both below 1 − α k 1-\alpha^k 1 − α k since α k + α k + 2 < α 2 \alpha^k+\alpha^{k+2}<\alpha^2 α k + α k + 2 < α 2 .
Suppose both child defects vanish. Their carry is nonnegative by the rotation arithmetic. Apart from 11, 24, 25, 59, the possibilities are
a ∈ { p , p + 1 , q } ∪ { q − 1 : j odd } , b ∈ { r , r + 1 , p } ∪ { p − 1 : j − 1 odd } . a \in\{p,p+1,q\} \cup\{q-1:j\text{ odd}\}, \qquad b \in\{r,r+1,p\} \cup\{p-1:j-1\text{ odd}\}. a ∈ { p , p + 1 , q } ∪ { q − 1 : j odd } , b ∈ { r , r + 1 , p } ∪ { p − 1 : j − 1 odd } .
We enumerate the zero-carry pairs.
For consecutive anchors write a = F k + 1 + s a=F_{k+1}+s a = F k + 1 + s , b = F k + t b=F_k+t b = F k + t , with s , t ∈ { − 1 , 0 , 1 } s,t\in\{-1,0,1\} s , t ∈ { − 1 , 0 , 1 } and offset − 1 -1 − 1 permitted only at odd orders. The offsets cannot both be − 1 -1 − 1 . If s + t = 0 s+t=0 s + t = 0 or 1 1 1 , n ∈ Z n\in\mathbb{Z} n ∈ Z . If s + t = 2 s+t=2 s + t = 2 , the fractional-part sum is 4 α − 2 + ( − 1 ) k − 1 α k + 2 < α 4\alpha-2+(-1)^{k-1}\alpha^{k+2}<\alpha 4 α − 2 + ( − 1 ) k − 1 α k + 2 < α , giving carry 1. If s + t = − 1 s+t=-1 s + t = − 1 and k k k is odd, again n ∈ Z n\in\mathbb{Z} n ∈ Z . If k k k is even, then ( s , t ) = ( − 1 , 0 ) (s,t)=(-1,0) ( s , t ) = ( − 1 , 0 ) and the sum α − α k + 2 \alpha-\alpha^{k+2} α − α k + 2 gives carry 1.
For anchors two ranks apart write a = q + s a=q+s a = q + s , b = r + t b=r+t b = r + t , where s ∈ { − 1 , 0 } s\in\{-1,0\} s ∈ { − 1 , 0 } and t ∈ { 0 , 1 } t\in\{0,1\} t ∈ { 0 , 1 } . A predecessor y y y satisfies y ≥ n − p = 2 r + s + t y\ge n-p=2r+s+t y ≥ n − p = 2 r + s + t but C ( y ) = r + t C(y)=r+t C ( y ) = r + t . Since α > 3 / 5 \alpha>3/5 α > 3/5 ,
3 5 ( 2 r + s + t + 1 ) − ( r + t + 1 ) = r + 3 s − 2 t − 2 5 ≥ r − 7 5 > 0. \frac{3}{5}(2r+s+t+1)-(r+t+1)=\frac{r+3s-2t-2}{5}\ge\frac{r-7}{5}>0. 5 3 ( 2 r + s + t + 1 ) − ( r + t + 1 ) = 5 r + 3 s − 2 t − 2 ≥ 5 r − 7 > 0.
contradicting C ( y ) ≥ G ( y ) C(y)\ge G(y) C ( y ) ≥ G ( y ) .
For the same anchor put p = F k p=F_k p = F k , k = j − 1 k=j-1 k = j − 1 , and B = 2 p − r = K k B=2p-r=K_k B = 2 p − r = K k . The pair ( p + 1 , p − 1 ) (p+1,p-1) ( p + 1 , p − 1 ) , allowed only for odd k k k , has carry 1 because 2 α − 1 + 2 α k < α 2\alpha-1+2\alpha^k<\alpha 2 α − 1 + 2 α k < α . The other pairs require
Table 1 (PDF p. 26).
The upper bounds on y y y come from capture, and the lower bounds follow from U ( y ) ≤ y − F k − 2 U(y)\le y-F_{k-2} U ( y ) ≤ y − F k − 2 . Each value saturates U ( y ) U(y) U ( y ) , contradicting (38) for k ≥ 8 k\ge8 k ≥ 8 . At the remaining order j = 8 j=8 j = 8 , ( 13 , 12 ) (13,12) ( 13 , 12 ) has sum 25 ∈ Z 25\in\mathbb{Z} 25 ∈ Z , ( 13 , 13 ) (13,13) ( 13 , 13 ) contradicts the strict center K 7 = 18 K_7=18 K 7 = 18 , and ( 14 , 12 ) (14,12) ( 14 , 12 ) has carry 1. The pair ( 14 , 13 ) (14,13) ( 14 , 13 ) at n = 27 n=27 n = 27 is excluded by the earlier values giving 14 ↦ 18 ↦ 15 ↦ 17 ↦ 15 14\mapsto18\mapsto15\mapsto17\mapsto15 14 ↦ 18 ↦ 15 ↦ 17 ↦ 15 , in which 14 is transient.
The exceptional children occur only in the following products of lists.
Table 5.
At q ≥ 233 q \ge233 q ≥ 233 , b ≥ 89 b \ge89 b ≥ 89 , so this list is exhaustive. Remove (13, 11), already in the base. Of the remaining twenty pairs,
( 25 , 14 ) , ( 35 , 25 ) , ( 59 , 35 ) , ( 90 , 59 ) (25, 14),\quad(35, 25),\quad(59, 35),\quad(90, 59) ( 25 , 14 ) , ( 35 , 25 ) , ( 59 , 35 ) , ( 90 , 59 )
have carry 1. The pairs (14, 11), (34, 25), (35, 24) have sums 25, 59, 59 in Z Z Z . The other thirteen are excluded as follows. All these floors are fixed by 55 / 89 < α < 89 / 144 55/89 < \alpha< 89/144 55/89 < α < 89/144 .
For (21, 11), (55, 24), (55, 25), (144, 59) the triples ( n , ℓ , G ( ℓ ) ) (n,\ell,G(\ell)) ( n , ℓ , G ( ℓ )) are
( 32 , 19 , 12 ) , ( 79 , 45 , 28 ) , ( 80 , 46 , 29 ) , ( 203 , 114 , 71 ) . (32, 19, 12),\quad(79, 45, 28),\quad(80, 46, 29),\quad(203, 114, 71). ( 32 , 19 , 12 ) , ( 79 , 45 , 28 ) , ( 80 , 46 , 29 ) , ( 203 , 114 , 71 ) .
A predecessor would have C ( y ) ≥ G ( ℓ ) > b C(y) \ge G(\ell) > b C ( y ) ≥ G ( ℓ ) > b . For three further pairs, two successive cycle predecessors give
Table 1 (PDF p. 27).
Here G ( 22 ) = 14 G(22)=14 G ( 22 ) = 14 or G ( 56 ) = 35 G(56)=35 G ( 56 ) = 35 forces y y y , and then the affine cap U ( z ) ≤ z − 8 U(z) \le z-8 U ( z ) ≤ z − 8 or z − 21 z-21 z − 21 forces z = a z=a z = a . Its required value is G ( a ) + 1 G(a)+1 G ( a ) + 1 , contradicting the zero-child assumption. This does not assume C ( 59 ) C(59) C ( 59 ) in advance. The pair (24, 14) at n = 38 n=38 n = 38 is excluded by 24 ↦ 23 ↦ 23 24 \mapsto23 \mapsto23 24 ↦ 23 ↦ 23 , using C ( 24 ) = C ( 23 ) = 15 C(24)=C(23)=15 C ( 24 ) = C ( 23 ) = 15 . For the next three pairs, the refined upper capture bound gives
Table 6.
The lower bounds on y y y follow from U ( y ) ≥ b U(y) \ge b U ( y ) ≥ b . But 29 = K 8 29=K_8 29 = K 8 and 76 = K 10 76=K_{10} 76 = K 10 , so the strict center and neighbor inequalities exclude these values.
The last two pairs require the prescribed depth, not just cyclicity. If T n ( H ) ⊆ J T_n(H) \subseteq J T n ( H ) ⊆ J and T n ( J ) ⊆ H T_n(J) \subseteq H T n ( J ) ⊆ H , an orbit starting in H H H is in H H H at even ranks. The needed intervals are
Table 2 (PDF p. 27).
The displayed comparisons prove the two inclusions. Since 57 ∉ Z 57 \notin Z 57 ∈ / Z , G ( 57 ) = 35 G(57)=35 G ( 57 ) = 35 and U ( 57 ) = 36 U(57)=36 U ( 57 ) = 36 , the depth at 58 is 36. Similarly, 147 ∉ Z 147 \notin Z 147 ∈ / Z , G ( 147 ) = 91 G(147)=91 G ( 147 ) = 91 and U ( 147 ) = 92 U(147)=92 U ( 147 ) = 92 force depth 92 at 148. Thus a ≥ 35 a \ge35 a ≥ 35 or 90, excluding ( 34 , 24 ) (34,24) ( 34 , 24 ) and ( 89 , 59 ) (89,59) ( 89 , 59 ) . This completes all cases, hence the simultaneous induction.
The reverse inclusion and landing
We now have ( P ) (P) ( P ) at every index. The equalities G ( F j ) = U ( F j ) = F j − 1 G(F_j)=U(F_j)=F_{j-1} G ( F j ) = U ( F j ) = F j − 1 and G ( F j + 1 ) = U ( F j + 1 ) = F j − 1 + 1 G(F_j+1)=U(F_j+1)=F_{j-1}+1 G ( F j + 1 ) = U ( F j + 1 ) = F j − 1 + 1 give the anchors. The strict cone and U ( F j − 1 ) = F j − 1 U(F_j-1)=F_{j-1} U ( F j − 1 ) = F j − 1 give the left neighbors for j ≥ 5 j \ge5 j ≥ 5 . When j j j is odd, these equal G ( F j − 1 ) G(F_j-1) G ( F j − 1 ) . The smaller cases are in the initial table.
The table gives C ( 11 ) = G ( 11 ) C(11)=G(11) C ( 11 ) = G ( 11 ) and C ( 24 ) = G ( 24 ) C(24)=G(24) C ( 24 ) = G ( 24 ) . At n = 25 n=25 n = 25 the orbit 24 ↦ 10 ↦ 18 ↦ 13 ↦ 17 ↦ 13 24 \mapsto10 \mapsto18 \mapsto13 \mapsto17 \mapsto13 24 ↦ 10 ↦ 18 ↦ 13 ↦ 17 ↦ 13 has transient 3, period 2 and depth 15, selecting 13. Thus C ( 25 ) = C ( 13 ) + C ( 12 ) = 16 = G ( 25 ) C(25)=C(13)+C(12)=16=G(25) C ( 25 ) = C ( 13 ) + C ( 12 ) = 16 = G ( 25 ) . At 59, the bounds and 58 ∉ Z 58 \notin Z 58 ∈ / Z force depth C ( 58 ) = 37 C(58)=37 C ( 58 ) = 37 . The intervals H = [ 37 , 58 ] H=[37,58] H = [ 37 , 58 ] and J = [ 1 , 35 ] J=[1,35] J = [ 1 , 35 ] alternate, since C ( 37 ) ≥ 24 C(37)\ge24 C ( 37 ) ≥ 24 by its strict lower bound, C ( x ) ≥ G ( 38 ) = 24 C(x)\ge G(38)=24 C ( x ) ≥ G ( 38 ) = 24 for x ≥ 38 x\ge38 x ≥ 38 , and C ( x ) ≤ U ( 35 ) = 22 C(x)\le U(35)=22 C ( x ) ≤ U ( 35 ) = 22 for x ≤ 35 x\le35 x ≤ 35 . Odd depth selects a ≤ 35 a\le35 a ≤ 35 . Capture also gives 34 ≤ a ≤ 38 34\le a\le38 34 ≤ a ≤ 38 , so a = 34 a=34 a = 34 or 35. Both give C ( 59 ) = 37 = G ( 59 ) C(59)=37=G(59) C ( 59 ) = 37 = G ( 59 ) using C ( 25 ) = 16 C(25)=16 C ( 25 ) = 16 and C ( 24 ) = 15 C(24)=15 C ( 24 ) = 15 . This proves the exact equality set.
At n = F k n=F_k n = F k , k ≥ 6 k\ge6 k ≥ 6 , capture with A = F k − 1 A=F_{k-1} A = F k − 1 makes the interval with endpoints A A A , n − F k − 2 n-F_{k-2} n − F k − 2 a singleton. Every orbit therefore reaches A A A , which is fixed by the anchor identity. Finally the lower bound gives lim inf C ( n ) / n ≥ α \liminf C(n)/n\ge\alpha lim inf C ( n ) / n ≥ α , and the Fibonacci subsequence gives the reverse inequality.
Proofs of the left plateau and of the right collar
Both proofs use Theorems 6 and 7 , the anchors (7) , and the capture and child localization in Theorem 10 and (36) , with inherited labels at Fibonacci endpoints. By Lemma 3 , g ( n ) g(n) g ( n ) lies on the cycle Γ n \Gamma_n Γ n reached from n − 1 n-1 n − 1 . The function G G G is nondecreasing and 1-Lipschitz, and U U U is nondecreasing.
The left plateau
Proof of Theorem 9 . Put L k ( u ) = F k − 1 − C ( F k − u ) L_k(u)=F_{k-1}-C(F_k-u) L k ( u ) = F k − 1 − C ( F k − u ) for 0 ≤ u ≤ F k − 2 0\le u\le F_{k-2} 0 ≤ u ≤ F k − 2 . We prove the stronger invariant
L k ( u ) = 0 ( 0 ≤ u ≤ w k ) , L k ( w k + 1 ) = 1 , 1 ≤ L k ( u ) ≤ u − w k − 1 ( w k + 2 ≤ u ≤ F k − 2 ) . (39) \begin{aligned}
L_k(u)&=0 &&(0\le u\le w_k),\\
L_k(w_k+1)&=1,\\
1\le L_k(u)&\le u-w_k-1 &&(w_k+2\le u\le F_{k-2}). \tag*{(39)}
\end{aligned} L k ( u ) L k ( w k + 1 ) 1 ≤ L k ( u ) = 0 = 1 , ≤ u − w k − 1 ( 0 ≤ u ≤ w k ) , ( w k + 2 ≤ u ≤ F k − 2 ) . (39)
A direct evaluation of the recursion through 55 gives the following vectors ( L k ( u ) ) 0 ≤ u ≤ F k − 2 (L_k(u))_{0\leq u\leq F_{k-2}} ( L k ( u ) ) 0 ≤ u ≤ F k − 2 .
These 45 values verify (39) for k = 8 , 9 , 10 k=8,9,10 k = 8 , 9 , 10 . The levels 9 and 10 initialize the induction below, whose parents satisfy n ≥ F 10 = 55 > 47 n\geq F_{10}=55>47 n ≥ F 10 = 55 > 47 .
Fix k ≥ 11 k\geq11 k ≥ 11 and suppose that (39) holds at the levels k − 1 k-1 k − 1 and k − 2 k-2 k − 2 . Write
A = F k − 1 , B = F k − 2 , P = F k − 3 , Q = F k − 4 . A=F_{k-1},\qquad B=F_{k-2},\qquad P=F_{k-3},\qquad Q=F_{k-4}. A = F k − 1 , B = F k − 2 , P = F k − 3 , Q = F k − 4 .
so that A = B + P A=B+P A = B + P and B = P + Q B=P+Q B = P + Q . Let n = F k − u n=F_k-u n = F k − u with 0 ≤ u ≤ B 0\leq u\leq B 0 ≤ u ≤ B . With the inherited label k − 1 k-1 k − 1 for the closed block [ A , F k ] [A,F_k] [ A , F k ] , the selected children satisfy g ( n ) ∈ [ B , A ] g(n)\in[B,A] g ( n ) ∈ [ B , A ] and n − g ( n ) ∈ [ P , B ] n-g(n)\in[P,B] n − g ( n ) ∈ [ P , B ] . In particular g ( n ) ∈ [ A − u , A ] g(n)\in[A-u,A] g ( n ) ∈ [ A − u , A ] .
The interval [ A − u , A ] [A-u,A] [ A − u , A ] is invariant under T n T_n T n . Indeed, if y = A − v y=A-v y = A − v with 0 ≤ v ≤ u 0\leq v\leq u 0 ≤ v ≤ u , then C ( y ) ≤ U ( A ) = B C(y)\leq U(A)=B C ( y ) ≤ U ( A ) = B , and C ( y ) ≥ G ( y ) ≥ G ( A ) − v = B − v ≥ B − u C(y)\geq G(y)\geq G(A)-v=B-v\geq B-u C ( y ) ≥ G ( y ) ≥ G ( A ) − v = B − v ≥ B − u . Hence A − u ≤ T n ( y ) ≤ A A-u\leq T_n(y)\leq A A − u ≤ T n ( y ) ≤ A . Since g ( n ) g(n) g ( n ) lies on Γ n \Gamma_n Γ n , the whole cycle lies in [ A − u , A ] [A-u,A] [ A − u , A ] . Capture at level k − 1 k-1 k − 1 also gives y ≥ B y\geq B y ≥ B on Γ n \Gamma_n Γ n , and for a cycle predecessor z z z of y y y the bounds G ( B ) = P G(B)=P G ( B ) = P and U ( A ) = B U(A)=B U ( A ) = B give n − y = C ( z ) ∈ [ P , B ] n-y=C(z)\in[P,B] n − y = C ( z ) ∈ [ P , B ] . Every cycle point can therefore be written y = A − v y=A-v y = A − v with
0 ≤ v ≤ u , v ≤ P , 0 ≤ u − v ≤ Q . (40) 0\leq v\leq u,\qquad v\leq P,\qquad0\leq u-v\leq Q. \tag*{(40)} 0 ≤ v ≤ u , v ≤ P , 0 ≤ u − v ≤ Q . (40)
In these coordinates the cycle map and the additivity at the selected point read
v ⟼ u − L k − 1 ( v ) , L k ( u ) = L k − 1 ( v ) + L k − 2 ( u − v ) . (41) v\longmapsto u-L_{k-1}(v),\qquad L_k(u)=L_{k-1}(v)+L_{k-2}(u-v). \tag*{(41)} v ⟼ u − L k − 1 ( v ) , L k ( u ) = L k − 1 ( v ) + L k − 2 ( u − v ) . (41)
Set w = w k − 1 w=w_{k-1} w = w k − 1 and z = w k − 2 z=w_{k-2} z = w k − 2 , so that z ≥ 2 z\geq2 z ≥ 2 . If 0 ≤ u ≤ w 0\leq u\leq w 0 ≤ u ≤ w , every accessible value L k − 1 ( v ) L_{k-1}(v) L k − 1 ( v ) is zero, every cycle point is sent to u u u , and the cycle is the fixed point v = u v=u v = u . Then (41) gives L k ( u ) = 0 L_k(u)=0 L k ( u ) = 0 .
Suppose that u ≥ w + 2 u\geq w+2 u ≥ w + 2 . No cycle point has v ≤ w v\leq w v ≤ w , since it would be sent to u u u . If u > P u>P u > P , this image is excluded by (40) . If u ≤ P u\leq P u ≤ P , the invariant at level k − 1 k-1 k − 1 gives 1 ≤ L k − 1 ( v ) ≤ u − w − 1 1\leq L_{k-1}(v)\leq u-w-1 1 ≤ L k − 1 ( v ) ≤ u − w − 1 for w < v ≤ u w<v\leq u w < v ≤ u , so after reaching u u u the orbit stays in [ w + 1 , u − 1 ] [w+1,u-1] [ w + 1 , u − 1 ] and cannot return to a point with v ≤ w v\leq w v ≤ w . A cycle point v = u v=u v = u would have a predecessor with zero defect, hence with offset at most w w w , which is excluded. Therefore w + 1 ≤ v ≤ u − 1 w+1\leq v\leq u-1 w + 1 ≤ v ≤ u − 1 on Γ n \Gamma_n Γ n . For u = w + 2 u=w+2 u = w + 2 the cycle is the fixed point v = w + 1 v=w+1 v = w + 1 , whose complementary offset is 1 ≤ z 1\leq z 1 ≤ z , and (41) gives
L k ( w + 2 ) = 1. (42) L_k(w+2)=1. \tag*{(42)} L k ( w + 2 ) = 1. (42)
For u ≥ w + 3 u\geq w+3 u ≥ w + 3 , put b = u − v ≥ 1 b=u-v\geq1 b = u − v ≥ 1 . If v = w + 1 v=w+1 v = w + 1 , then b ≥ 2 b\geq2 b ≥ 2 , and the invariant at level k − 2 k-2 k − 2 with z ≥ 2 z\geq2 z ≥ 2 gives L k − 2 ( b ) ≤ b − 2 L_{k-2}(b)\leq b-2 L k − 2 ( b ) ≤ b − 2 , so L k ( u ) ≤ 1 + ( b − 2 ) = u − w − 2 L_k(u)\leq1+(b-2)=u-w-2 L k ( u ) ≤ 1 + ( b − 2 ) = u − w − 2 . If v ≥ w + 2 v\geq w+2 v ≥ w + 2 , the bounds L k − 1 ( v ) ≤ v − w − 1 L_{k-1}(v)\leq v-w-1 L k − 1 ( v ) ≤ v − w − 1 and L k − 2 ( b ) ≤ b − 1 L_{k-2}(b)\leq b-1 L k − 2 ( b ) ≤ b − 1 give the same estimate. In both cases L k − 1 ( v ) ≥ 1 L_{k-1}(v)\geq1 L k − 1 ( v ) ≥ 1 , hence
1 ≤ L k ( u ) ≤ u − w − 2 ( w + 3 ≤ u ≤ B ) . (43) 1\leq L_k(u)\leq u-w-2\qquad(w+3\leq u\leq B). \tag*{(43)} 1 ≤ L k ( u ) ≤ u − w − 2 ( w + 3 ≤ u ≤ B ) . (43)
It remains to determine L k ( w + 1 ) L_k(w+1) L k ( w + 1 ) . The defect at level k − 1 k-1 k − 1 vanishes through w w w and equals 1 at w + 1 w+1 w + 1 , so the only cycle of (41) in the allowed range is { w , w + 1 } \{w,w+1\} { w , w + 1 } . In the original coordinates its vertices are ℓ = A − w − 1 \ell=A-w-1 ℓ = A − w − 1 and r = A − w = ℓ + 1 r=A-w=\ell+1 r = A − w = ℓ + 1 . The invariant at level k − 1 k-1 k − 1 gives the barriers
y < r ⇒ C ( y ) ≤ B − 1 , y ≥ r ⇒ C ( y ) ≥ B . (44) y<r\Rightarrow C(y)\le B-1,\qquad y\ge r\Rightarrow C(y)\ge B. \tag*{(44)} y < r ⇒ C ( y ) ≤ B − 1 , y ≥ r ⇒ C ( y ) ≥ B . (44)
For B ≤ y < r B\le y<r B ≤ y < r the first one is the positivity of the defect at level k − 1 k-1 k − 1 , and for y < B y<B y < B it follows from C ( y ) ≤ U ( B ) = P < B C(y)\le U(B)=P<B C ( y ) ≤ U ( B ) = P < B . For r ≤ y ≤ A r\le y\le A r ≤ y ≤ A the second one is the plateau at level k − 1 k-1 k − 1 , and for y > A y>A y > A it follows from C ( y ) ≥ G ( A ) = B C(y)\ge G(A)=B C ( y ) ≥ G ( A ) = B . Since n = A + B − w − 1 n=A+B-w-1 n = A + B − w − 1 , the barriers give
y ≥ r ⇒ T n ( y ) ≤ ℓ , y ≤ ℓ ⇒ T n ( y ) ≥ r . y\ge r\Rightarrow T_n(y)\le\ell,\qquad y\le\ell\Rightarrow T_n(y)\ge r. y ≥ r ⇒ T n ( y ) ≤ ℓ , y ≤ ℓ ⇒ T n ( y ) ≥ r .
The orbit starts at n − 1 = r + B − 2 ≥ r n-1=r+B-2\ge r n − 1 = r + B − 2 ≥ r and alternates between the two sides. Once it has reached the cycle, it visits r r r exactly at even ranks. By (42) , the depth at this parent is h n = C ( n − 1 ) = A − L k ( w + 2 ) = A − 1 h_n=C(n-1)=A-L_k(w+2)=A-1 h n = C ( n − 1 ) = A − L k ( w + 2 ) = A − 1 . This is not circular, since (42) was obtained from the two previous profiles without the value at w + 1 w+1 w + 1 . If A A A is odd, the depth is even, the selected point is r r r with offset w w w , and L k ( w + 1 ) = 0 L_k(w+1)=0 L k ( w + 1 ) = 0 . If A A A is even, the selected point is ℓ \ell ℓ with offset w + 1 w+1 w + 1 , and L k ( w + 1 ) = 1 L_k(w+1)=1 L k ( w + 1 ) = 1 .
Consequently w k = w k − 1 + 1 { F k − 1 odd } w_k=w_{k-1}+\mathbf{1}_{\{F_{k-1}\text{ odd}\}} w k = w k − 1 + 1 { F k − 1 odd } . Since F j F_j F j is even exactly when 3 divides j j j , the formula w k = ⌊ ( 2 k − 9 ) / 3 ⌋ w_k=\lfloor(2k-9)/3\rfloor w k = ⌊( 2 k − 9 ) /3 ⌋ satisfies this recurrence and the initial values. Equations (42) and (43) give the value 1 just beyond the new plateau and the affine bound of (39) , whether the plateau advances or not. This completes the induction.
Finally, if m < F k − 1 m<F_{k-1} m < F k − 1 , then C ( m ) ≤ U ( F k − 1 ) = F k − 2 < F k − 1 C(m)\le U(F_{k-1})=F_{k-2}<F_{k-1} C ( m ) ≤ U ( F k − 1 ) = F k − 2 < F k − 1 . The invariant excludes every index of [ F k − 1 , F k − w k ) [F_{k-1},F_k-w_k) [ F k − 1 , F k − w k ) , and the plateau starts at F k − w k F_k-w_k F k − w k . This gives the first occurrence.
The right collar
Let n = F k + t ≥ 47 n=F_k+t\ge47 n = F k + t ≥ 47 with 0 ≤ t ≤ F k − 1 0\le t\le F_{k-1} 0 ≤ t ≤ F k − 1 , and write g ( n ) = F k − 1 + s g(n)=F_{k-1}+s g ( n ) = F k − 1 + s with inherited labels. Capture and child localization give 0 ≤ s ≤ t 0\le s\le t 0 ≤ s ≤ t , s ≤ F k − 2 s\le F_{k-2} s ≤ F k − 2 and t − s ≤ F k − 3 t-s\le F_{k-3} t − s ≤ F k − 3 , and Theorem 10 gives E k ( t ) = E k − 1 ( s ) + E k − 2 ( t − s ) E_k(t)=E_{k-1}(s)+E_{k-2}(t-s) E k ( t ) = E k − 1 ( s ) + E k − 2 ( t − s ) , where all defects are nonnegative by the cap. Before entering the captured interval, the orbit may leave the range where P k − 1 P_{k-1} P k − 1 is used. For that purpose put P ~ k − 1 ( u ) = C ( F k − 1 + u ) − F k − 2 \widetilde{P}_{k-1}(u)=C(F_{k-1}+u)-F_{k-2} P k − 1 ( u ) = C ( F k − 1 + u ) − F k − 2 whenever 1 ≤ F k − 1 + u ≤ n − 1 1\le F_{k-1}+u\le n-1 1 ≤ F k − 1 + u ≤ n − 1 . In the coordinate y = F k − 1 + u y=F_{k-1}+u y = F k − 1 + u the map T n T_n T n becomes u ↦ t − P ~ k − 1 ( u ) u\mapsto t-\widetilde{P}_{k-1}(u) u ↦ t − P k − 1 ( u ) , and the monotonicity of U U U and G G G together with the anchors gives the barriers
P ~ k − 1 ( u ) ≤ 0 ( u < 0 ) , P ~ k − 1 ( u ) ≥ 1 ( u > 0 ) . (45) \widetilde{P}_{k-1}(u)\le0\quad(u<0),\qquad\widetilde{P}_{k-1}(u)\ge1\quad(u>0). \tag*{(45)} P k − 1 ( u ) ≤ 0 ( u < 0 ) , P k − 1 ( u ) ≥ 1 ( u > 0 ) . (45)
Lemma 24 (Transmission of a first defect). Let 1 ≤ t ≤ F k − 3 1\le t\le F_{k-3} 1 ≤ t ≤ F k − 3 with F k + t ≥ 47 F_k+t\ge47 F k + t ≥ 47 , and suppose that E j ( u ) = 0 E_j(u)=0 E j ( u ) = 0 for 0 ≤ u < t 0\le u<t 0 ≤ u < t and j ∈ { k , k − 1 , k − 2 } j\in\{k,k-1,k-2\} j ∈ { k , k − 1 , k − 2 } . If E k ( t ) > 0 E_k(t)>0 E k ( t ) > 0 , then
E k − 1 ( t ) = 0 , E k ( t ) = E k − 2 ( t ) > 0 , g ( F k + t ) = F k − 1 , F k − 1 ≡ t ( m o d 2 ) . E_{k-1}(t)=0,\qquad E_k(t)=E_{k-2}(t)>0,\qquad g(F_k+t)=F_{k-1},\qquad F_{k-1}\equiv t\pmod{2}. E k − 1 ( t ) = 0 , E k ( t ) = E k − 2 ( t ) > 0 , g ( F k + t ) = F k − 1 , F k − 1 ≡ t ( mod 2 ) .
Proof. Write A = F k − 1 A=F_{k-1} A = F k − 1 and B = F k − 2 B=F_{k-2} B = F k − 2 . The hypotheses force k ≥ 10 k\ge10 k ≥ 10 , so B > 1 B>1 B > 1 . Every cycle lies in the coordinate interval [ 0 , t ] [0,t] [ 0 , t ] , and the selected point is cyclic.
Suppose first that E k − 1 ( t ) > 0 E_{k-1}(t)>0 E k − 1 ( t ) > 0 . Since P k − 1 ( t ) ≥ 1 P_{k-1}(t)\ge1 P k − 1 ( t ) ≥ 1 , the integer E k − 1 ( t ) E_{k-1}(t) E k − 1 ( t ) lies in [ 1 , t − 1 ] [1,t-1] [ 1 , t − 1 ] . For 0 ≤ u < t 0\le u<t 0 ≤ u < t the map is u ↦ t − u u\mapsto t-u u ↦ t − u , and the image of t t t is E k − 1 ( t ) E_{k-1}(t) E k − 1 ( t ) . Thus 0 0 0 has no preimage in [ 0 , t ] [0,t] [ 0 , t ] , and the only preimage of t t t there is 0 0 0 . Neither endpoint is cyclic, so 0 < s < t 0<s<t 0 < s < t , and both terms of the profile identity vanish, contrary to E k ( t ) > 0 E_k(t)>0 E k ( t ) > 0 . Hence E k − 1 ( t ) = 0 E_{k-1}(t)=0 E k − 1 ( t ) = 0 .
The map on [ 0 , t ] [0,t] [ 0 , t ] is now the reflection u ↦ t − u u\mapsto t-u u ↦ t − u . If s > 0 s>0 s > 0 , then E k − 1 ( s ) = 0 E_{k-1}(s)=0 E k − 1 ( s ) = 0 and E k − 2 ( t − s ) = 0 E_{k-2}(t-s)=0 E k − 2 ( t − s ) = 0 , which again contradicts E k ( t ) > 0 E_k(t)>0 E k ( t ) > 0 . Hence s = 0 s=0 s = 0 and E k ( t ) = E k − 2 ( t ) > 0 E_k(t)=E_{k-2}(t)>0 E k ( t ) = E k − 2 ( t ) > 0 .
It remains to find the parity of the selected rank. The initial coordinate is u 0 = n − 1 − A = B + t − 1 > t u_0=n-1-A=B+t-1>t u 0 = n − 1 − A = B + t − 1 > t . By (45) , before its first entry into [ 0 , t ] [0,t] [ 0 , t ] the orbit lies above t t t at even ranks and below 0 0 0 at odd ranks. An entry at a point of ( 0 , t ) (0,t) ( 0 , t ) stays in ( 0 , t ) (0,t) ( 0 , t ) under the reflection and cannot reach the endpoint cycle { 0 , t } \{0,t\} { 0 , t } . An entry into that cycle therefore happens at 0 0 0 at an odd rank or at t t t at an even rank, and in both cases every visit to 0 0 0 has odd rank. Since the selected offset is 0 0 0 , the depth h F k + t h_{F_k+t} h F k + t is odd. The collar at t − 1 t-1 t − 1 gives h F k + t = C ( F k + t − 1 ) = A + t − 1 h_{F_k+t}=C(F_k+t-1)=A+t-1 h F k + t = C ( F k + t − 1 ) = A + t − 1 , hence A ≡ t ( m o d 2 ) A\equiv t\pmod{2} A ≡ t ( mod 2 ) .
Proof of Proposition 12. For t ≥ 0 t\ge0 t ≥ 0 put K t = 8 + 6 t K_t=8+6t K t = 8 + 6 t . We prove by induction on t t t that E k ( u ) = 0 E_k(u)=0 E k ( u ) = 0 for 0 ≤ u ≤ t 0\le u\le t 0 ≤ u ≤ t and every k ≥ K t k\ge K_t k ≥ K t . The case t = 0 t=0 t = 0 is the anchor C ( F k ) = F k − 1 C(F_k)=F_{k-1} C ( F k ) = F k − 1 . Let t ≥ 1 t\ge1 t ≥ 1 , assume the assertion for t − 1 t-1 t − 1 , fix k ≥ K t k\ge K_t k ≥ K t and suppose that E k ( t ) > 0 E_k(t)>0 E k ( t ) > 0 . We apply Lemma 24 at the levels k k k , k − 2 k-2 k − 2 and k − 4 k-4 k − 4 . The lowest profile index involved is k − 6 ≥ K t − 1 k-6\ge K_{t-1} k − 6 ≥ K t − 1 , which gives the collar hypotheses. The offset hypotheses follow from t ≤ F 6 t + 1 ≤ F k − 7 t\le F_{6t+1}\le F_{k-7} t ≤ F 6 t + 1 ≤ F k − 7 , and the lowest parent level is k − 4 ≥ 10 k-4\ge10 k − 4 ≥ 10 , so every parent exceeds 47. The lemma gives E k − 2 ( t ) > 0 E_{k-2}(t)>0 E k − 2 ( t ) > 0 , then E k − 4 ( t ) > 0 E_{k-4}(t)>0 E k − 4 ( t ) > 0 , and
F k − 1 ≡ F k − 3 ≡ F k − 5 ≡ t ( m o d 2 ) . F_{k-1}\equiv F_{k-3}\equiv F_{k-5}\equiv t \pmod{2}. F k − 1 ≡ F k − 3 ≡ F k − 5 ≡ t ( mod 2 ) .
The indices k − 1 k-1 k − 1 , k − 3 k-3 k − 3 and k − 5 k-5 k − 5 represent the three residue classes modulo 3, so exactly one of these Fibonacci numbers is even, a contradiction. Hence E k ( t ) = 0 E_k(t)=0 E k ( t ) = 0 , and the smaller offsets are covered by the induction hypothesis.
The Campbell formula and its orbit rows
Define B ( 1 ) = 1 B(1)=1 B ( 1 ) = 1 and define B ( n ) B(n) B ( n ) by the right side of (4) for n ≥ 2 n\ge2 n ≥ 2 . Its scale is unique because the respective half-open intervals partition the eligible even and odd indices. Directly,
1 ≤ B ( n ) ≤ n − 1 , B ( n ) ≡ n + 1 ( m o d 2 ) ( n ≥ 2 ) . (46) 1\le B(n)\le n-1,\qquad B(n)\equiv n+1\pmod{2}\quad(n\ge2). \tag*{(46)} 1 ≤ B ( n ) ≤ n − 1 , B ( n ) ≡ n + 1 ( mod 2 ) ( n ≥ 2 ) . (46)
The following four rules hold on closed intervals, and the formulas agree at every shared endpoint. In each row t t t is a power of 3. At x = 6 t x=6t x = 6 t , for instance, the next even scale 3 t 3t 3 t gives the same value 3 t 3t 3 t , and at x = 9 t x=9t x = 9 t the next odd scale gives 6 t 6t 6 t .
Table 7.
Fix n n n and put U n ( x ) = n − B ( x ) U_n(x)=n-B(x) U n ( x ) = n − B ( x ) on 1 ≤ x ≤ n − 1 1\le x\le n-1 1 ≤ x ≤ n − 1 . By (46) , this interval is invariant. Write x 0 = n − 1 x_0=n-1 x 0 = n − 1 and x j + 1 = U n ( x j ) x_{j+1}=U_n(x_j) x j + 1 = U n ( x j ) .
Lemma 25. Let s ≥ 3 s\ge3 s ≥ 3 be a power of 3 in the interval associated with n n n . The orbit is given by the tables below. In particular, U n 6 ( n − 1 ) = U n 4 ( n − 1 ) U_n^6(n-1)=U_n^4(n-1) U n 6 ( n − 1 ) = U n 4 ( n − 1 ) . If n n n is even then x 4 = B ( n ) x_4=B(n) x 4 = B ( n ) , and if n n n is odd then x 5 = B ( n ) x_5=B(n) x 5 = B ( n ) .
In the first table set
A = min ( n − 2 s / 3 , 5 s / 3 + 1 ) , B = min ( n − 2 s / 3 , 2 s ) . A=\min(n-2s/3,5s/3+1), \qquad B=\min(n-2s/3,2s). A = min ( n − 2 s /3 , 5 s /3 + 1 ) , B = min ( n − 2 s /3 , 2 s ) .
Rows are closed for convenience, and are intersected with 2 s ≤ n < 6 s 2s\le n<6s 2 s ≤ n < 6 s or 3 s ≤ n < 9 s 3s\le n<9s 3 s ≤ n < 9 s , respectively. Adjacent rows agree at shared endpoints.
Table 8.
Table 9.
Proof. Use the four branch rules with t = s / 3 t=s/3 t = s /3 , s s s , 3 s 3s 3 s , all powers of 3 3 3 . The parities alternate for even n n n , starting with odd x 0 x_0 x 0 , and for odd n n n all indices x j x_j x j are even. All listed arguments remain in [ 1 , n − 1 ] [1,n-1] [ 1 , n − 1 ] .
We detail E1, which involves the two minima. Here 5 s / 3 ≤ 2 s − 1 ≤ n − 1 ≤ 3 s 5s/3 \le2s-1 \le n-1 \le3s 5 s /3 ≤ 2 s − 1 ≤ n − 1 ≤ 3 s , so the odd linear branch at scale s / 3 s/3 s /3 gives B ( n − 1 ) = n − s − 1 B(n-1)=n-s-1 B ( n − 1 ) = n − s − 1 and x 1 = s + 1 x_1=s+1 x 1 = s + 1 . Since 2 s / 3 ≤ s + 1 ≤ 4 s / 3 2s/3 \le s+1 \le4s/3 2 s /3 ≤ s + 1 ≤ 4 s /3 , we get B ( x 1 ) = 2 s / 3 + 1 B(x_1)=2s/3+1 B ( x 1 ) = 2 s /3 + 1 and x 2 = n − 2 s / 3 − 1 x_2=n-2s/3-1 x 2 = n − 2 s /3 − 1 . This odd index lies in [ s , 3 s ] [s,3s] [ s , 3 s ] , and hence
B ( x 2 ) = max ( 2 s / 3 , n − 5 s / 3 − 1 ) , x 3 = A . B(x_2)=\max(2s/3,n-5s/3-1), \qquad x_3=A. B ( x 2 ) = max ( 2 s /3 , n − 5 s /3 − 1 ) , x 3 = A .
Both arguments defining A A A are at least 4 s / 3 4s/3 4 s /3 , and A ≤ 5 s / 3 + 1 ≤ 2 s A \le5s/3+1 \le2s A ≤ 5 s /3 + 1 ≤ 2 s . The even plateau at scale s / 3 s/3 s /3 therefore gives B ( x 3 ) = s B(x_3)=s B ( x 3 ) = s and x 4 = n − s x_4=n-s x 4 = n − s . This odd index lies in [ s , 3 s ] [s,3s] [ s , 3 s ] , so B ( x 4 ) = max ( 2 s / 3 , n − 2 s ) B(x_4)=\max(2s/3,n-2s) B ( x 4 ) = max ( 2 s /3 , n − 2 s ) and x 5 = B x_5=B x 5 = B . Finally, 4 s / 3 ≤ B ≤ 2 s 4s/3 \le B \le2s 4 s /3 ≤ B ≤ 2 s gives B ( x 5 ) = s B(x_5)=s B ( x 5 ) = s and x 6 = n − s x_6=n-s x 6 = n − s .
The remaining rows follow by the same substitutions. To illustrate the change of scale in O7, x 1 = 3 s + 1 x_1=3s+1 x 1 = 3 s + 1 gives B ( x 1 ) = 2 s + 1 B(x_1)=2s+1 B ( x 1 ) = 2 s + 1 , so x 2 = n − 2 s − 1 ∈ [ 6 s , 7 s − 1 ] x_2=n-2s-1 \in[6s,7s-1] x 2 = n − 2 s − 1 ∈ [ 6 s , 7 s − 1 ] . The even linear branch at scale 3 s 3s 3 s gives B ( x 2 ) = n − 5 s − 1 B(x_2)=n-5s-1 B ( x 2 ) = n − 5 s − 1 and x 3 = 5 s + 1 x_3=5s+1 x 3 = 5 s + 1 . The even plateau at scale s s s then gives x 4 = n − 3 s x_4=n-3s x 4 = n − 3 s , which lies in [ 5 s + 1 , 6 s ] [5s+1,6s] [ 5 s + 1 , 6 s ] and is fixed by U n U_n U n . Each of the other rows uses the displayed branch intervals directly.
Induction for the formula
We prove b ( n ) = B ( n ) b(n)=B(n) b ( n ) = B ( n ) by strong induction. Direct evaluation through n = 8 n=8 n = 8 gives ( 1 , 1 , 2 , 3 , 2 , 3 , 4 , 5 ) (1,1,2,3,2,3,4,5) ( 1 , 1 , 2 , 3 , 2 , 3 , 4 , 5 ) , as required. For n ≥ 9 n \ge9 n ≥ 9 , assume equality at every smaller index. Then T n = U n T_n=U_n T n = U n throughout [ 1 , n − 1 ] [1,n-1] [ 1 , n − 1 ] . Since this interval is invariant, their entire starting orbits agree.
Let d = b ( n − 1 ) = B ( n − 1 ) d=b(n-1)=B(n-1) d = b ( n − 1 ) = B ( n − 1 ) . Equation (46) gives d ≡ n ( m o d 2 ) d \equiv n \pmod{2} d ≡ n ( mod 2 ) . For even n ≥ 10 n \ge10 n ≥ 10 , the table gives d ≥ 4 d \ge4 d ≥ 4 , since d = n − s − 1 ≥ n / 2 − 1 ≥ 4 d=n-s-1 \ge n/2-1 \ge4 d = n − s − 1 ≥ n /2 − 1 ≥ 4 in E1, d = 2 s ≥ 6 d=2s \ge6 d = 2 s ≥ 6 in E2–E4, and d = n − 3 s − 1 ≥ 2 s ≥ 6 d=n-3s-1 \ge2s \ge6 d = n − 3 s − 1 ≥ 2 s ≥ 6 in E5. For odd n n n , it gives d ≥ 5 d \ge5 d ≥ 5 , since d = n − s − 1 ≥ 2 s − 1 ≥ 5 d=n-s-1 \ge2s-1 \ge5 d = n − s − 1 ≥ 2 s − 1 ≥ 5 in O1, d = 3 s ≥ 9 d=3s \ge9 d = 3 s ≥ 9 in O2–O4, and d = n − 3 s − 1 ≥ 3 s ≥ 9 d=n-3s-1 \ge3s \ge9 d = n − 3 s − 1 ≥ 3 s ≥ 9 in O5–O7.
Since x 6 = x 4 x_6=x_4 x 6 = x 4 , determinism implies x j + 2 = x j x_{j+2}=x_j x j + 2 = x j for every j ≥ 4 j \ge4 j ≥ 4 . For even n n n , d d d is even and at least four, so b ( n ) = x d = x 4 = B ( n ) b(n)=x_d=x_4=B(n) b ( n ) = x d = x 4 = B ( n ) . For odd n n n , d d d is odd and at least five, so b ( n ) = x d = x 5 = B ( n ) b(n)=x_d=x_5=B(n) b ( n ) = x d = x 5 = B ( n ) . This closes the induction.
The same lemma proves T n 6 ( n − 1 ) = T n 4 ( n − 1 ) T_n^{6}(n-1)=T_n^{4}(n-1) T n 6 ( n − 1 ) = T n 4 ( n − 1 ) for n ≥ 9 n \ge9 n ≥ 9 . For n = 2 , 3 , 4 , 5 , 6 , 7 , 8 n=2,3,4,5,6,7,8 n = 2 , 3 , 4 , 5 , 6 , 7 , 8 , direct calculation gives x 4 = x 6 x_4=x_6 x 4 = x 6 equal to 1 , 2 , 3 , 4 , 3 , 4 , 5 1,2,3,4,3,4,5 1 , 2 , 3 , 4 , 3 , 4 , 5 , respectively. The bound four is attained at n = 24 n=24 n = 24 , with the orbit
23 ⟼ 10 ⟼ 17 ⟼ 16 ⟼ 15 ⟼ 18 ⟼ 15 ⟼ 18 ⟼ ⋯ 23 \longmapsto10 \longmapsto17 \longmapsto16 \longmapsto15 \longmapsto18 \longmapsto15 \longmapsto18 \longmapsto\cdots 23 ⟼ 10 ⟼ 17 ⟼ 16 ⟼ 15 ⟼ 18 ⟼ 15 ⟼ 18 ⟼ ⋯
The first six displayed values are distinct. This finishes the proof of Theorem 4 .
Scaling and periods
Corollary 26. For every n ≥ 2 n \ge2 n ≥ 2 , b ( 3 n ) = 3 b ( n ) b(3n) = 3b(n) b ( 3 n ) = 3 b ( n ) . Moreover,
lim inf n → ∞ b ( n ) n = 2 5 , lim sup n → ∞ b ( n ) n = 3 4 . \liminf_{n\to\infty}\frac{b(n)}{n} = \frac{2}{5}, \qquad\limsup_{n\to\infty}\frac{b(n)}{n} = \frac{3}{4}. n → ∞ lim inf n b ( n ) = 5 2 , n → ∞ lim sup n b ( n ) = 4 3 .
Proof. Multiplying n n n by 3 3 3 preserves parity, sends its scale s s s to 3 s 3s 3 s , and multiplies either expression in (4) by 3 3 3 . On even indices, b ( n ) / n ∈ [ 1 / 2 , 3 / 4 ] b(n)/n \in[1/2,3/4] b ( n ) / n ∈ [ 1/2 , 3/4 ] , and on odd indices it lies in [ 2 / 5 , 2 / 3 ] [2/5,2/3] [ 2/5 , 2/3 ] . The values n = 5 ⋅ 3 k n = 5 \cdot3^k n = 5 ⋅ 3 k attain 2 / 5 2/5 2/5 , and n = 4 ⋅ 3 k n = 4 \cdot3^k n = 4 ⋅ 3 k attain 3 / 4 3/4 3/4 , proving the two limits.
For even n ≥ 4 n \ge4 n ≥ 4 , the eventual period is exactly two, since the two phases have opposite parity. At n = 2 n = 2 n = 2 the orbit is fixed. For odd n n n , the tables give
x 4 = { n − s , 3 s ≤ n ≤ 5 s , 4 s , 5 s ≤ n ≤ 7 s , n − 3 s , 7 s ≤ n < 9 s , x 5 = max ( 2 s , n − 3 s ) . x_4 =
\begin{cases}
n-s, & 3s \le n \le5s,\\
4s, & 5s \le n \le7s,\\
n-3s, & 7s \le n < 9s,
\end{cases}
\qquad x_5 = \max(2s,n-3s). x 4 = ⎩ ⎨ ⎧ n − s , 4 s , n − 3 s , 3 s ≤ n ≤ 5 s , 5 s ≤ n ≤ 7 s , 7 s ≤ n < 9 s , x 5 = max ( 2 s , n − 3 s ) .
Consequently the prescribed orbit is eventually fixed exactly when n = 3 s n = 3s n = 3 s or 7 s ≤ n < 9 s 7s \le n < 9s 7 s ≤ n < 9 s . At the other odd indices its period is two. The small scale s = 1 s = 1 s = 1 agrees by direct calculation at n = 3 , 5 , 7 n = 3,5,7 n = 3 , 5 , 7 .
2020 Mathematics Subject Classification : 11B37; 11B39; 68W30.
Keywords : nested recurrences, meta-recursions, Fibonacci numbers, Hofstadter sequences, Pascal words.