Connecting slow solutions to nested recurrences with linear recurrent sequences

DOI10.1080/10236198.2022.2152335MaRDI QIDQ5870247zbMATH OpenOpenAlexFDO

Authors Nathan Fox

Publication date 6 January 2023

Published in Journal of Difference Equations and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.09340

zbMATH Keywords

FibonacciHofstadter sequencenested recurrenceslowly growing solutiontreeZeckendorf representation

Mathematics Subject Classification ID

Trees (05C05) Recurrences (11B37) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Number-theoretic algorithms; complexity (11Y16)

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.

Recommendations

• Constructing new families of nested recursions with slow solutions
• Nested recurrence relations with Conolly-like solutions
• A fast algorithm for solving linearly recurrent sequences
• scientific article; zbMATH DE number 1577994
• On the solution of linear recurrence equations
• On solving linear recurrences
• On nearly linear recurrence sequences
• Solutions of linear recurrence equations
• On the Solution of Linear Mean Recurrences
• scientific article; zbMATH DE number 7136391

Cites work

• A combinatorial approach for constructing non-monotonic solutions to the generalized Golomb recursion
• A combinatorial approach for solving certain nested recursions with non-slow solutions
• A new approach to the Hofstadter \(Q\)-recurrence
• A slow relative of Hofstadter's \(Q\)-sequence
• A well-behaved cousin of the Hofstadter sequence
• Constructing new families of nested recursions with slow solutions
• Conway's Challenge Sequence
• Discovering linear-recurrent solutions to Hofstadter-like recurrences using symbolic computation
• Fibonacci meets Hofstadter
• From Fibonacci numbers to central limit type theorems
• scientific article; zbMATH DE number 5577875 (Why is no real title available?)
• scientific article; zbMATH DE number 1185867 (Why is no real title available?)
• scientific article; zbMATH DE number 5274232 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• Linear recurrent subsequences of generalized meta-Fibonacci sequences
• Nested recurrence relations with Conolly-like solutions
• Nested recursions with ceiling function solutions
• Nested recursions, simultaneous parameters and tree superpositions
• Quasipolynomial solutions to the Hofstadter Q-recurrence
• Solving non-homogeneous nested recursions using trees
• Trees and meta-Fibonacci sequences

Cited in

(1)

• A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Connecting slow solutions to nested recurrences with linear recurrent sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870247)