Trees and meta-Fibonacci sequences
Summary: For \(k > 1\) and nonnegative integer parameters \(a_p, b_p, p = 1..k\), we analyze the solutions to the meta-Fibonacci recursion \(C(n) = \sum^k_{p=1} C (n - a_p - C (n - b_p))\), where the parameters \(a_p, b_p, p = 1..k\) satisfy a specific constraint. For \(k = 2\) we present compelling empirical evidence that solutions exist only for two particular families of parameters; special cases of the recursions so defined include the Conolly recursion and all of its generalizations that have been studied to date. We show that the solutions for all the recursions defined by the parameters in these families have a natural combinatorial interpretation: they count the number of labels on the leaves of certain infinite labeled trees, where the number of labels on each node in the tree is determined by the parameters. This combinatorial interpretation enables us to determine various new results concerning these sequences, including a closed form, and to derive asymptotic estimates. Our results broadly generalize and unify recent findings of this type relating to certain of these meta-Fibonacci sequences. At the same time they indicate the potential for developing an analogous counting interpretation for many other meta-Fibonacci recursions specified by the same recursion for \(C(n)\) with other sets of parameters.
- Discovering linear-recurrent solutions to Hofstadter-like recurrences using symbolic computation
- On Hofstadter heart sequences
- On a conjecture about generalized \(Q\)-recurrence
- On a generalization of Hofstadter's Q-sequence: a family of chaotic generational structures
- Solving non-homogeneous nested recursions using trees
- Constructing new families of nested recursions with slow solutions
- On families of solutions for meta-Fibonacci recursions related to Hofstadter-Conway \$10000 sequence
- A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence
- How the shift parameter affects the behavior of a family of meta-Fibonacci sequences
- Generalized meta-Fibonacci sequences
- scientific article; zbMATH DE number 3961638 (Why is no real title available?)
- Nested recursions, simultaneous parameters and tree superpositions
- On the solution space of the Golomb recursion
- A new approach to the Hofstadter \(Q\)-recurrence
- A combinatorial interpretation of Hofstadter's G-sequence
- A combinatorial problem solved by a meta-Fibonacci recurrence relation
- On the Behavior of a Family of Meta-Fibonacci Sequences
- A combinatorial approach for constructing non-monotonic solutions to the generalized Golomb recursion
- On variants of Conway and Conolly's meta-Fibonacci recursions
- Connecting slow solutions to nested recurrences with linear recurrent sequences
- Solutions of certain meta-Fibonacci recurrences
- Meta-automatic sequences
- Meta-Fibonacci sequences, binary trees and extremal compact codes
This page was built for publication: Trees and meta-Fibonacci sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380294)
