Nested Recurrence Relations With Conolly-Like Solutions

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)$-Conollyifithasan$(\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\mathrm{.}Forthecasewhere$\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.