Increasing Self-Described Sequences

Y.-F.S. Pétermann^{1} and Jean-Luc Rémy^{2}

Petermann@math.unige.ch

Jean-Luc.Remy@loria.fr

Annals of Combinatorics 8 (3) p.325-346 September, 2004

Abstract:

We proceed with our study of increasing
self-described sequences *F*, beginning with 1 and defined by a functional
equation and *F*_{i}
denoting ). In [1] we exhibited
the simple solution , for some
, of the associated functional-differential
equation , and we proved that
provided , where , we have the asymptotic
equivalence .
1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6,
6, 7, ...,
for which the boundary case holds,
does not satisfy . We also show
that the m-th term F(m) of a sequence F for which the boundary case holds
is nevertheless of asymptotic order .
1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10,
10, 11, ... .

In the present paper we show that this last result
is optimal, in the sense that the self-described sequence defined by ,
that is

Then we investigate the behaviour of self-described
sequences *F* when lies beyond the boundary case.
In [1] we established the estimates
when is the unique fixed point
of a certain associated function. We were only able to prove in general that
the latter holds when does *not*
lie beyond the boundary case, however. In the present paper we prove that whenever
is the unique fixed point of this function, and in addition we obtain estimates
more precise than . This applies
for instance to the sequence defined by ,
that is

References:

1. Y.-F.S. Pétermann, J.-L. Rémy, and I. Vardi, Discrete derivatives of sequences, Adv. Appl. Math. 27 (2001) 562--584.