Connecting slow solutions to nested recurrences with linear recurrent sequences

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.

Keywords:

• Nested recurrence
• Hofstadter sequence
• slowly growing solution
• tree
• Fibonacci
• Zeckendorf representation

Maths:

• 11B37
• 11B39
• 05C05
• 11Y16

Disclosure statement

The authors report there are no competing interests to declare.

Notes

1 Several authors prefer the convention where $C_s(n)=C_s(n-s+1-C_s(n-1))+C_s(n-s-C_s(n-2))$, adding 1 to each of our s values.