Connecting slow solutions to nested recurrences with linear recurrent sequences. Issue 11 (2nd December 2022)

• Record Type: Journal Article
• Authors: Fox, Nathan
• Is Part Of: Journal of difference equations and applications. Volume 28:Issue 11/12(2022)
• Page Start: 1458
• Page End: 1491
• Publication Date: 2022-12-02
• Subjects: Nested recurrence -- Hofstadter sequence -- slowly growing solution -- tree -- Fibonacci -- Zeckendorf representation; 11B37 -- 11B39 -- 05C05 -- 11Y16; Difference equations -- Periodicals; 515.625
• DOI: 10.1080/10236198.2022.2152335
• Languages: English
• ISSNs: 1023-6198

Abstract

Abstract : Labeled infinite trees provide combinatorial interpretations for many integer sequences generated by nested recurrence relations. Typically, such sequences are monotone increasing. Several of these sequences also have straightforward descriptions in terms of how often each value in the sequence occurs. In this paper, we generalize the most classical examples to a larger family of sequences parametrized by linear recurrence relations. Each of our sequences can be constructed in three different ways: via a nested recurrence relation, from labeled infinite trees, or by using Zeckendorf-like strings of digits to describe its frequency sequence. We conclude the paper by discussing the asymptotic behaviors of our sequences.