Nested Recurrence Relations With Conolly-Like Solutions

Abstract

A nondecreasing sequence of positive integers is $(\alpha ,\beta )$-Conolly, or Conolly-like for short, if for every positive integer $m$ the number of times that $m$ occurs in the sequence is $\alpha +\beta r_m$, where $r_m$ is $1$ plus the 2-adic valuation of $m$. A recurrence relation is $(\alpha ,\beta )$-Conolly if it has an $(\alpha ,\beta )$-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)={\sum }_{i=1}^{k}A(n-s_i-{\sum }_{j=1}^{p_i}A(n-a_{ij}))$ with appropriate initial conditions. For any fixed integers $k$ and $p_1,p_2,\dots ,p_k$ we prove that there are only finitely many pairs $(\alpha ,\beta )$ for which $A(n)$ can be $(\alpha ,\beta )$-Conolly. For the case where $\alpha =0$ and $\beta =1$, 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 $(\alpha ,\beta )$-Conolly recursion for every possible ($\alpha ,\beta )$ 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.

References in corpus (1)

• A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

Cited by in corpus (1)

• A New Approach to the Hofstadter $Q$-Recurrence