A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

zbMATH Open1148.05005arXiv0801.1097MaRDI QIDQ3536752FDOQ3536752

Stephen M. Tanny, Zhiqiang Li, B. Balamohan

Publication date: 21 November 2008

Abstract: For any integer s >= 0, we derive a combinatorial interpretation for the family of sequences generated by the recursion (parameterized by s) h_s(n) = h_s(n - s - h_s(n - 1)) + h_s(n - 2 - s - h_s(n - 3)), n > s + 3, with the initial conditions h_s(1) = h_s(2) = ... = h_s(s+2) = 1 and h_s(s+3) = 2. We show how these sequences count the number of leaves of a certain infinite tree structure. Using this interpretation we prove that h_s sequences are "slowly growing", that is, h_s sequences are monotone nondecreasing, with successive terms increasing by 0 or 1, so each sequence hits every positive integer. Further, for fixed s the sequence h_s(n) hits every positive integer twice except for powers of 2, all of which are hit s+2 times. Our combinatorial interpretation provides a simple approach for deriving the ordinary generating functions for these sequences.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Nested recurrence relations with Conolly-like solutions
• Trees and meta-Fibonacci sequences
• On variants of Conway and Conolly's meta-Fibonacci recursions
• A combinatorial interpretation of Hofstadter's \(G\)-sequence
• Connecting slow solutions to nested recurrences with linear recurrent sequences

zbMATH Keywords

ordinary generating functionHofstadter sequencemeta-Fibonacci recursionslowly growing sequences

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Recurrences (11B37) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cited In (3)

• Nested recursions, simultaneous parameters and tree superpositions
• Solving non-homogeneous nested recursions using trees
• Constructing new families of nested recursions with slow solutions

Uses Software

• OEIS

This page was built for publication: A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

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