Nested Recurrence Relations With ConollyLike 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 selfreferencing recurrence relations of the form
\[A(n) = \sum_{i=1}^k A(ns_i\sum_{j=1}^{p_i} A(na_{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 2adic valuation of $m$.
In general, a nondecreasing sequence is Conollylike
if the number of times
that m occurs is $\alpha + \beta r_m$ for some integers
$\alpha$ and $\beta$, and a recurrence relation is
Conollylike if it has a Conollylike solution sequence.
In the case where $k=2$, $p_i = 1$ we characterize all Conollylike
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 Conollylike recursions for other
values of α and β.
For general $k$, $p_i$, we prove the existence of Conollylike 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 metaFibonacci sequences with $p_i > 1$.

Download: pdf file.

SIAM J. Discrete Mathematics, 26 2012, pp. 206238 (33 pages).

Submitted May 14, 2010; accepted July 7, 2011.

Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.

Selected citations:
Back to list of publications.