Nested Recurrence Relations With Conolly-Like Solutions

Abraham Isgur, Department of Mathematics, University of Toronto, Canada.
Alejandro Erickson, Department of Computer Science, University of Victoria, Canada.
Brad Jackson, Department of Mathematics, San Jose State University, USA.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Steve Tanny, Department of Mathematics, University of Toronto, Canada.

Abstract:

This paper is concerned with a family of sequences described by self-referencing 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 various initial conditions. In the case where $k = 2$, $p_i = 1$, $s_1 = 0$, $a_{11} = 1$, $s_2 = 1$, and $a_{21} = 2$, with initial conditions $A(1)=A(2)=1$, this is known as the Conolly recurrence relation and its solution is monotone with successive values that are either equal or increase by one, such that the number of times that the integer $m$ occurs in the sequence $A(1), A(2), A(3),\ldots$ is $1 + r_m$, where $r_m$ is the 2-adic valuation of $m$. In general, a non-decreasing sequence is Conolly-like if the number of times that m occurs is $\alpha + \beta r_m$ for some integers $\alpha$ and $\beta$, and a recurrence relation is Conolly-like if it has a Conolly-like solution sequence. In the case where $k=2$, $p_i = 1$ we characterize all Conolly-like recursions for β = 0, α = 2, provide strong experimental evidence that we have discovered all Conolly like recursions with β=1, α = 0, and prove that there are no Conolly-like recursions for other values of α and β. For general $k$, $p_i$, we prove the existence of Conolly-like recurrence relations for α even and nonnegative and β nonnegative, and provide strong experimental evidence of the existence of some other Conolly like classes. In addition, this allows us to give the first known complete characterization of a number of meta-Fibonacci sequences with $p_i > 1$.

Back to list of publications.