ABSTRACT
We show how to modify the tree-based methodology to construct a combinatorial interpretation for certain non-monotonic solutions to recursions in the generalized Golomb family . Using this combinatorial interpretation we derive the asymptotic properties of these solutions.
AMS CLASSIFICATIONS:
Disclosure statement
No potential conflict of interest was reported by the authors.
Notes
1. It is well known that a nested recursion need not have a solution for every set of initial conditions. For example, Golomb's recursion with the initial condition has no solution, since
, which is undefined.
2. Note that this is not the only non-preorder labelling of that causes its leaf label counting function solution to be non-monotonic for a pre-order traversal of the tree. For fixed values of the parameters it can be shown that there are several ways to define a non-preorder labelling on the skeleton of
, each of which yields a slightly different non-monotonic solution but with identical asymptotic properties.
3. Note that label 54 is not a leaf label of as the node containing it is not a leaf node of
in our sense.
4. Observe that the tree , whose leaf label counting function
solves (Equation1
(1)
(1) ), is not the same as the tree
defined in the Introduction with leaf label counting function
. The labelling of
is more useful than that of
, it does not have any special nodes with two labels, and it generalizes more readily for other values of the parameters. Thus we base the labelling of the tree
on that of
rather than on the labelling of
. In Section 5 we show that
for sufficiently large n.
5. The pruning operation can be defined for with n>s + 2j, which guarantees that label n is at least in the second bough of
. However we only require it to be defined for
in order to prove Theorem 4.4.
6. In fact, both Proposition 3.1 and Corollary 3.2 which follows from it hold for . For such n it is necessarily the case that label n is at least in the fourth bough of
and that label n will have a node above it and in the same branch when label n is in a penultimate node or leaf node of
.
7. In fact, both these lemmas, as well as the preceding one, hold for (that is, label n is at least in the fourth bough of
and has a node above it and in the same branch when label n is in a penultimate node or leaf node of
. The more relaxed results are sufficient for our purposes.