Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond

Source abstract

Hofstadter's G function is recursively defined via G(0) = 0 and then G(n) = n-G(G(n -1)). Following Hofstadter, we vary the number k of nested recursive calls in this equation and obtain a family of functions (F\_k). In a previous article, we proved that this family is ordered pointwise: for all k and n, we have $F_k(n)$le$F_{k+1}(n)$. Here we propose a much shorter proof of this theorem, without infinite morphic words. The key ingredient for this direct proof is a new formula expressing iterates of the preimages of $F_k$ . Thanks to this formula, we also prove several conjectures mentioned in our previous article. In particular we obtain that $F_k(n) (k + 1)(k + 6)/2. We provide a certified formalization of all these results in the Rocq proof assistant.