Nested recurrence relations with Conolly-like solutions

DOI10.1137/100795425zbMATH Open1260.11010arXiv1509.02613OpenAlexW2131975287MaRDI QIDQ2902898FDOQ2902898

Authors: Alejandro Erickson, Abraham Isgur, Frank Ruskey, Bradley W. Jackson, Stephen M. Tanny 

Publication date: 22 August 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A nondecreasing sequence of positive integers is $$-Conolly, or Conolly-like for short, if for every positive integer $m$ the number of times that $m$ occurs in the sequence is $$, where $r_m$ is $1$ plus the 2-adic valuation of $m$. A recurrence relation is $$-Conolly if it has an $$-Conolly solution sequence. We discover that Conolly-like sequences often appear as solutions to nested (or meta-Fibonacci) recurrence relations of the form $A(n)=su{m}_{i=1}^{k}A(n-s_i-su{m}_{j=1}^{p_i}A(n-a_{ij}))$ with appropriate initial conditions. For any fixed integers $k$ and $p_1,p_2,ldots,p_k$ we prove that there are only finitely many pairs $$ for which $A(n)$ can be $$-Conolly. For the case where $alpha=0$ and $$, we provide a bijective proof using labelled infinite trees to show that, in addition to the original Conolly recurrence, the recurrence $H(n)=H(n-H(n-2))+H(n-3-H(n-5))$ also has the Conolly sequence as a solution. When $k=2$ and $p_1=p_2$, we construct an example of an $$-Conolly recursion for every possible ($$ pair, thereby providing the first examples of nested recursions with $p_i>1$ whose solutions are completely understood. Finally, in the case where $k=2$ and $p_1=p_2$, we provide an if and only if condition for a given nested recurrence $A(n)$ to be $(alpha,0)$-Conolly by proving a very general ceiling function identity.

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

Recommendations

• A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence
• On variants of Conway and Conolly's meta-Fibonacci recursions
• ‘Golomb-like’ nested recursions with Beatty function solutions
• Solving non-homogeneous nested recursions using trees
• Sums of ceiling functions solve nested recursions

zbMATH Keywords

bijective proofinfinite treesnested recursionmeta-Fibonacciceiling function identityConolly-likeruler functionself-referencing recursionslowly growing sequence

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Recurrences (11B37)

Cited In (11)

• Nested recursions, simultaneous parameters and tree superpositions
• On a conjecture about generalized \(Q\)-recurrence
• Connecting slow solutions to nested recurrences with linear recurrent sequences
• Sums of ceiling functions solve nested recursions
• Solving non-homogeneous nested recursions using trees
• ‘Golomb-like’ nested recursions with Beatty function solutions
• Nested recursions with ceiling function solutions
• Discovering linear-recurrent solutions to Hofstadter-like recurrences using symbolic computation
• Constructing new families of nested recursions with slow solutions
• A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence
• A new approach to the Hofstadter \(Q\)-recurrence

This page was built for publication: Nested recurrence relations with Conolly-like solutions

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