An exploration of solutions to two related Hofstadter-Huber recurrence relations

Abstract

In this study, we explore the properties of certain solutions of two Hofstadter-Huber recurrence relations. The first is Hofstadter's V-recurrence, which is defined by the nested recurrence relation V(n) = V(n - V (n - 1)) + V (n - V (n - 4)) . Plus, we introduce another meta-Fibonacci recurrence H(n) = H(n - H(n - 2)) + H(n - H(n - 3)) . First, we study a finite chaotic solution to the V-recurrence in order to analyse its generational structure. Then, we explore a new type of infinite solution to nested recurrence relations, finding solutions of this type to both the V-recurrence and the H-recurrence. Our construction relates to systems of nested recurrences that resemble Golomb's recurrence G(n) = G(n - G(n - 1)) + 1 . (C) 2020 Elsevier Ltd. All rights reserved.