Nested recurrence relations with Conolly-like solutions

DOI10.1137/100795425MaRDI QIDQ2902898zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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)