A combinatorial approach for constructing non-monotonic solutions to the generalized Golomb recursion

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 $g_{s,j,\lambda }\left(n\right)=g_{s,j,\lambda }(n-s-g_{s,j,\lambda }(n-j\left)\right)+\lambda j$. Using this combinatorial interpretation we derive the asymptotic properties of these solutions.

KEYWORDS:

• Non-homogeneous nested recursion
• generalized Golomb recursion
• non-monotonic
• meta-Fibonacci Sequence
• tree-based methodology
• combinatorial counting argument

AMS CLASSIFICATIONS:

• Primary 05A19
• 11B37
• Secondary 05A15
• 05C05

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 $g\left(1\right)=2$ has no solution, since $g\left(2\right)=g(2-g(1\left)\right)+1=g\left(0\right)+1$, which is undefined.

2. Note that this is not the only non-preorder labelling of ${\mathcal{T}}_{s,j,\lambda }$ 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 ${\mathcal{T}}_{s,j,\lambda }$, 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 ${\mathcal{T}}_{1,2,3}\left(54\right)$ as the node containing it is not a leaf node of ${\mathcal{T}}_{1,2,3}\left(54\right)$ in our sense.

4. Observe that the tree ${\mathcal{T}}_{0,1,1}$, whose leaf label counting function $L_{{\mathcal{T}}_{0,1,1}}\left(n\right)$ solves (1(1) $g\left(n\right)=g(n-g(n-1\left)\right)+1,$(1) ), is not the same as the tree ${\mathcal{G}}^{\prime }$ defined in the Introduction with leaf label counting function $g^{\prime }\left(n\right)$. The labelling of ${\mathcal{T}}_{0,1,1}$ is more useful than that of ${\mathcal{G}}^{\prime }$, 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 ${\mathcal{T}}_{s,j,\lambda }$ on that of ${\mathcal{T}}_{0,1,1}$ rather than on the labelling of ${\mathcal{G}}^{\prime }$. In Section 5 we show that $g^{\prime }\left(n\right)=L_{{\mathcal{T}}_{0,1,1}}\left(n\right)$ for sufficiently large n.

5. The pruning operation can be defined for ${\mathcal{T}}_{s,j,\lambda }\left(n\right)$ with n>s + 2j, which guarantees that label n is at least in the second bough of ${\mathcal{T}}_{s,j,\lambda }$. However we only require it to be defined for $n>4s+6j(\lambda +1)$ in order to prove Theorem 4.4.

6. In fact, both Proposition 3.1 and Corollary 3.2 which follows from it hold for $n>3s+5j+3\lambda j$. For such n it is necessarily the case that label n is at least in the fourth bough of ${\mathcal{T}}_{s,j,\lambda }\left(n\right)$ 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 ${\mathcal{T}}_{s,j,\lambda }\left(n\right)$.

7. In fact, both these lemmas, as well as the preceding one, hold for $n>3s+5j+3\lambda j$ (that is, label n is at least in the fourth bough of ${\mathcal{T}}_{s,j,\lambda }\left(n\right)$ and has a node above it and in the same branch when label n is in a penultimate node or leaf node of ${\mathcal{T}}_{s,j,\lambda }\left(n\right)$. The more relaxed results are sufficient for our purposes.