A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

B. Balamohan, Zhiqiang Li, and Stephen Tanny^{1} Department of Mathematics University of Toronto Toronto, Ontario M5S 2E4 Canada

               bbalamoh@math.utoronto.ca
                zhiqiang.li@utoronto.ca
                tanny@math.utoronto.ca

Abstract

For any integer s ≥ 0, we derive a combinatorial interpretation for the family of sequences generated by the recursion (parameterized by s) h_{s}(n) = h_{s}(n − s − h_{s}(n − 1)) + h_{s}(n − 2 − s − h_{s}(n − 3)), n > s + 3, with the initial conditions h_{s}(1) = h_{s}(2) = ⋯ = h_{s}(s + 2) = 1 and h_{s}(s + 3) = 2. We show how these sequences count the number of leaves of a certain infinite tree structure. Using this interpretation we prove that h_{s} sequences are “slowly growing”, that is, h_{s} sequences are monotone nondecreasing, with successive terms increasing by 0 or 1, so each sequence hits every positive integer. Further, for fixed s the sequence h_{s}(n) hits every positive integer twice except for powers of 2, all of which are hit s + 2 times. Our combinatorial interpretation provides a simple approach for deriving the ordinary generating functions for these sequences.

1 Introduction

Conolly [2] introduced the sequence defined by the meta-Fibonacci (self-referencing) recursion

F (n) = F (n − F (n − 1)) + F (n − 1 − F (n − 2)),  n > 2  (1.1)

with initial conditions (F (1) = 0, F (2) = 1) or (F (1) = 1, F (2) = 1). He notes that for n > 2 the recursion yields the same sequence whether F (1) = 0 or F (1) = 1. The resulting sequence behaves in a very simple fashion: it is monotonic non-decreasing, with successive terms differing by either 0 or 1, so the sequence hits every positive integer. Following Ruskey [8] we term such a sequence “slowly growing”.

1Corresponding author.

Variants and generalizations of the recursion (1.1) and its initial conditions have been studied (see, for example, [1, 4, 6, 10]). The most comprehensive of these is the following k-term generalization, where s and k ≥ 2 are nonnegative integers:

T_{s,k}(n) = ∑_{i=0}^{k−1} T_{s,k}(n − i − s − T_{s,k}(n − i − 1)),  n > s + k.  (1.2)

The special case of (1.2) for s = 1 and initial conditions T_{1,k}(1) = T_{1,k}(2) = 1, and T_{1,k}(j) = j − 1 for 3 ≤ j ≤ k + 1 is first discussed by Higham and Tanny [6]. It is shown there that the resulting sequence is slowly growing.

Recently Jackson and Ruskey [7] (and see [3] for a generalization) derived a beautiful combinatorial interpretation for the sequences generated by (1.2) with initial conditions T_{s,k}(j) = 1 for 1 ≤ j ≤ s + 1, and T_{s,k}(j) = j − s for s + 2 ≤ j ≤ s + k. These initial conditions are natural extensions for arbitrary s of those appearing in [6]. Using their interpretation they show that all of these sequences are slowly growing.

Even further, Jackson and Ruskey’s interpretation provides a highly intuitive understanding for the similarity of these sequences for fixed k and varying values of the “shift” parameter s, a fact that had been noted by others but never proved. For fixed k the only differences between the sequences T_{s,k}(n) and T_{0,k}(n) occur in the frequencies with which each sequence hits the powers of k. More precisely, for fixed k and any positive integer r, the value k^{r} occurs s more times in the sequence T_{s,k}(n) than in the sequence T_{0,k}(n).

The present work is inspired by their approach. We begin with a meta-Fibonacci recursion closely related to (1.2), namely,

h_{s,k}(n) = ∑_{j=0}^{k−1} h_{s,k}(n − 2j − s − h_{s,k}(n − (2j + 1))),  n > s + 2k + 1.  (1.3)

The right hand side of (1.3) includes precisely those terms in the sum on the right hand side of (1.2) that derive from the even values of the index. For k > 2 there does not appear to be any set of initial conditions for which (1.3) generates an interesting infinite sequence. For k = 2, however, (1.3) reduces to the two term recurrence

h_{s}(n) = h_{s}(n − s − h_{s}(n − 1)) + h_{s}(n − 2 − s − h_{s}(n − 3)),  n > s + 3.  (1.4)

For any integer s ≥ 0 we derive a combinatorial interpretation for the sequence generated by the recursion (1.4) with the initial values h_{s}(1) = h_{s}(2) = ⋯ = h_{s}(s + 2) = 1 and h_{s}(s + 3) = 2. These initial conditions are the natural analogue of the ones described above by Deugau and Ruskey [3]. It turns out that this sequence is slowly growing. Further, the role played by the parameter s in this family of sequences appears to be the same as in the generalized Conolly recursion analyzed by Deugau and Ruskey [3]. For given s each sequence h_{s}(n) hits every positive integer twice except for the powers of 2, all of which are hit (s + 2) times in the sequence. See Table 1.1 for the first 50 terms of each sequence for 0 ≤ s ≤ 6.

Table 1.1: First 50 entries of h_{s} for 0 ≤ s ≤ 6.

\begin{matrix}n\s & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 \\ 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 \\ 5 & 3 & 2 & 2 & 1 & 1 & 1 & 1 \\ 6 & 3 & 2 & 2 & 2 & 1 & 1 & 1 \\ 7 & 4 & 3 & 2 & 2 & 2 & 1 & 1 \\ 8 & 4 & 3 & 2 & 2 & 2 & 2 & 1 \\ 9 & 5 & 4 & 3 & 2 & 2 & 2 & 2 \\ 10 & 5 & 4 & 3 & 2 & 2 & 2 & 2 \\ 11 & 6 & 4 & 4 & 3 & 2 & 2 & 2 \\ 12 & 6 & 5 & 4 & 3 & 2 & 2 & 2 \\ 13 & 7 & 5 & 4 & 4 & 3 & 2 & 2 \\ 14 & 7 & 6 & 4 & 4 & 3 & 2 & 2 \\ 15 & 8 & 6 & 5 & 4 & 4 & 3 & 2 \\ 16 & 8 & 7 & 5 & 4 & 4 & 3 & 2 \\ 17 & 9 & 7 & 6 & 4 & 4 & 4 & 3 \\ 18 & 9 & 8 & 6 & 5 & 4 & 4 & 3 \\ 19 & 10 & 8 & 7 & 5 & 4 & 4 & 4 \\ 20 & 10 & 8 & 7 & 6 & 4 & 4 & 4 \\ 21 & 11 & 9 & 8 & 6 & 5 & 4 & 4 \\ 22 & 11 & 9 & 8 & 7 & 5 & 4 & 4 \\ 23 & 12 & 10 & 8 & 7 & 6 & 4 & 4 \\ 24 & 12 & 10 & 8 & 8 & 6 & 5 & 4 \\ 25 & 13 & 11 & 9 & 8 & 7 & 5 & 4 \\ 26 & 13 & 11 & 9 & 8 & 7 & 6 & 4 \\ 27 & 14 & 12 & 10 & 8 & 8 & 6 & 5 \\ 28 & 14 & 12 & 10 & 8 & 8 & 7 & 5 \\ 29 & 15 & 13 & 11 & 9 & 8 & 7 & 6 \\ 30 & 15 & 13 & 11 & 9 & 8 & 8 & 6 \\ 31 & 16 & 14 & 12 & 10 & 8 & 8 & 7 \\ 32 & 16 & 14 & 12 & 10 & 8 & 8 & 7 \\ 33 & 17 & 15 & 13 & 11 & 9 & 8 & 8 \\ 34 & 17 & 15 & 13 & 11 & 9 & 8 & 8 \\ 35 & 18 & 16 & 14 & 12 & 10 & 8 & 8 \\ 36 & 18 & 16 & 14 & 12 & 10 & 8 & 8 \\ 37 & 19 & 16 & 15 & 13 & 11 & 9 & 8 \\ 38 & 19 & 17 & 15 & 13 & 11 & 9 & 8 \\ 39 & 20 & 17 & 16 & 14 & 12 & 10 & 8 \\ 40 & 20 & 18 & 16 & 14 & 12 & 10 & 8 \\ 41 & 21 & 18 & 16 & 15 & 13 & 11 & 9 \\ 42 & 21 & 19 & 16 & 15 & 13 & 11 & 9 \\ 43 & 22 & 19 & 17 & 16 & 14 & 12 & 10 \\ 44 & 22 & 20 & 17 & 16 & 14 & 12 & 10 \\ 45 & 23 & 20 & 18 & 16 & 15 & 13 & 11 \\ 46 & 23 & 21 & 18 & 16 & 15 & 13 & 11 \\ 47 & 24 & 21 & 19 & 16 & 16 & 14 & 12 \\ 48 & 24 & 22 & 19 & 17 & 16 & 14 & 12 \\ 49 & 25 & 22 & 20 & 17 & 16 & 15 & 13 \\ 50 & 25 & 23 & 20 & 18 & 17 & 15 & 13 \end{matrix}

In Section 2 we show how the sequence {h_{s}(n)}_{n=1}^{∞} can be interpreted in terms of the leaves in an infinite tree structure, from which the properties stated above follow readily. This interpretation also allows us to derive the generating function for this sequence in Section 3. We provide some final thoughts in Section 4.

2 Tree Structure

We begin this section by constructing a tree structure T_{s} that consists of an infinite number of rooted trees joined together at their respective roots plus a single initial isolated node. Subsequently we show how to label the vertices in T_{s} so that for any s ≥ 0 the number of leaves up to the vertex with label n in this infinite tree structure is equal to h_{s}(n).

Figure 2.1 shows the initial portion of T_{s}. To create T_{s} first we join an infinite chain of nodes {s_{i}}_{i=1}^{∞}, with node s_{i+1} connected to node s_{i} for i = 1, 2, . . .. We say that these nodes, which we distinguish by the term super-nodes, are at level 0 in the graph. Each super-node s_{i} is the root of a subtree of T_{s} and has 2^{i−1} children, or level 1 nodes. Each level 1 node has one child, so a level 2 node. Level 2 nodes have no children, hence these nodes are called leaves. Denote by S_{i}, i = 1, 2, … the rooted tree consisting of the root s_{i} and all its descendants (level 1 and level 2 nodes). Finally we complete T_{s} by adding an isolated node I. Note that I is itself a leaf of a trivial tree, but is not of level 0, 1 or 2. As usual, for a graph G, let V (G) denote the set of nodes (vertices) of G. Call the subgraph of T_{s} induced by {I} ∪ ⋃_{k=1}^{i} V (S_{k}) the ith complete partial graph.

Figure 2.1: The initial portion of T_{s} with s = 0.

Figure 2.2: The initial portion of T_{s} with s = 1.

Figure 2.3: The initial portion of T_{s} with s = 2.

We now label each node with the integers 1, 2, 3, … in the following way. Label I, the isolated node, 1. All super-nodes, starting with s_{1}, have the smallest s consecutive labels not yet used, where s is the parameter of the sequence h_{s}(n) that we are considering. Note that if s = 0 the super-nodes have no labels. So for s ≥ 1 the first super-node s_{1} is labelled 2, 3, …, s + 1, which are the next s consecutive integers. Label each of the level 1 and level 2 nodes of the subtree S_{1} with a single integer, in increasing order first from level 1 to level 2 nodes and then from left to right. Do the same thing for S_{2}, S_{3} and so on. See Figures 2.1, 2.2 and 2.3 where we show the initial portion of T_{s} for s = 0, 1, 2, respectively.

Denote by v_{s}(n) the node with label n. Let T_{s}(n) be the subgraph of T_{s} induced by {v_{s}(i) : 1 ≤ i ≤ n}. Observe that if v_{s}(n) = v_{s}(n − 1) = s_{i} for some i, we have T_{s}(n) = T_{s}(n − 1). Note that the isolated node I is a leaf of T_{s}(n) for all n = 1, 2, . . .. Let a_{s}(n) be the number of leaves of T in T_{s}(n). That is, a_{s}(n) equals the number of level 2 nodes in T_{s}(n) plus 1 (for the isolated node I). Finally, define d_{s}(n) to be 1 if v_{s}(n) is a leaf of T_{s} and to be 0 otherwise. Then it follows directly from these definitions that

a_{s}(n) = ∑_{k=1}^{n} d_{s}(k).  (2.1)

It is immediate from (2.1) that the sequence {a_{s}(n)}_{n=1}^{∞} is slowly growing. In addition

Lemma 2.1. The sequence {a_{s}(n)}_{n=1}^{∞} satisfies the following properties:

(a) Let s > 0 and r ≥ 1. Suppose n is the rth label in a super-node. Then for −r ≤ i ≤ s + 1 − r, a_{s}(n − r − 1) + 1 = a_{s}(n + i) = a_{s}(n − r + s + 2) − 1.

(b) If v_{s}(n) is a level 1 node, then a_{s}(n − 1) = a_{s}(n) = a_{s}(n + 1) − 1.

(c) If v_{s}(n) is a level 2 node, then a_{s}(n − 1) + 1 = a_{s}(n) = a_{s}(n + 1).

Proof. (a) Observe that if n is the r-th label in a super-node, then n−r +1 and n−r +s are the first and last labels respectively in this super-node. Further, v_{s}(n − r) is the last node in the immediately preceding complete partial graph, so is a leaf. Thus, v_{s}(n − r − 1) is the parent of this leaf and is a child of a super-node. It follows from (2.1) and our definitions that a_{s}(n − r − 1) + 1 counts the number of leaves in that preceding complete subtree.

Since −r ≤ i ≤ s + 1 − r, then n − r ≤ n + i ≤ n − r + s + 1. All the values of n + i lie between the label of the last leaf in the immediately preceding complete subtree and the label of the first child of this super-node. Thus,

a_{s}(n − r − 1) + 1 = a_{s}(n + i) = a_{s}(n − r + s + 2) − 1.

Both (b) and (c) are immediate from the definitions of level 1 and level 2 and (2.1).

Lemma 2.2. For i ≥ 1, 1 ≤ r ≤ 2^{i−1},

(a) If v_{s}(n) is the super-node s_{i} (written compactly v_{s}(n) = s_{i}), then a_{s}(n) = 2^{i−1}.

(b) If v_{s}(n) is a level 1 node, the rth child of s_{i}, then a_{s}(n) = 2^{i−1} + r − 1.

(c) If v_{s}(n) is a level 2 node, a leaf whose parent is the rth child of s_{i}, then a_{s}(n) = 2^{i−1} + r.

Proof. If v_{s}(n) = s_{i}, a_{s}(n) counts the number of leaves in the (i − 1)st complete partial graph. So

a_{s}(n) = 1 + ∑_{k=1}^{i−1} 2^{k−1} = 2^{i−1}.  (2.2)

The other two cases follow readily.

Figure 2.4: The chopping process P

For any T_{s}(n), we define a chopping process P that removes and rearranges nodes in the following way (see Figure 2.4): begin by removing the first super-node s_{1} and all leaves of T_{s} (including the isolated node I). Then let the only child of s_{1} (which is not removed) be the new isolated node I, and every second level 1 node in S_{i} (i > 1) be the child of its neighboring sibling on the left. Finally, relabel the tree so obtained in the same way as we label T_{s}.

We observe several properties of the chopping process P:

• P1. The tree T_{s} is invariant under P. One still gets T_{s} after applying P on T_{s}. See Figure 2.4.

• P2. Apply P on the ith complete partial graph, i > 1. We get the (i − 1)st complete partial graph.

• P3. For any n ≥ s + 4, apply P on T_{s}(n) (the subgraph T_{s}(n) strictly contains the first complete subgraph). The resulting reduced graph is T_{s}(n − s − a_{s}(n)), which has s + a_{s}(n) fewer labels (note that n − s − a_{s}(n) > 0 by construction). For i > 1, T_{s}(n) contains S_{i} if and only if T_{s}(n − s − a_{s}(n)) contains S_{i−1}. See Figure 2.5 where we apply P to T_{3}(19) and get T_{3}(19 − 3 − a_{3}(19)) = T_{3}(11).

Now we state our main theorem:

Theorem 2.3. The sequence h_{s}(n) defined by (1.4) and the given initial conditions counts the number of leaves in T_{s}(n). More precisely, for every positive integer n, h_{s}(n) = a_{s}(n).

Figure 2.5: The chopping process P reduces T_{3}(19) to T_{3}(11).

Proof. We proceed by induction on n for fixed s. We first show that the assertion holds for the initial values n = 1, 2, …, 2s + 7. These comprise all the labels in the first two rooted trees S_{1} and S_{2} (together with I).

For n = 1, 2, …, s + 2, h_{s}(n) = 1 by the initial conditions assumed for (1.4), while a_{s}(n) = 1 because the isolated node I has label 1 and counts as a leaf, the super-node s_{1} has s labels and its only child is labeled s + 2. For n = s + 3 a_{s}(n) = 2 because the node labeled s+3 is the first (and only) leaf in S_{1}. Further, for n = s+4, …, 2s+4, a_{s}(n) = 2 because the super-node s_{2} contains s labels starting with s+4 and the node labeled 2s+4 is the first child of s_{2}. But for the range of values n = s+3, …, 2s+4 we can apply induction to the recursion for h_{s}(n) to get h_{s}(n) = h_{s}(n − s − h_{s}(n − 1)) + h_{s}(n − 2 − s − h_{s}(n − 3)) = 1 + 1 = 2 = a_{s}(n), as desired. The next two labels n = 2s + 5 and 2s + 6 are assigned to the first leaf in S_{2} and the second child of s_{2}, respectively, so it follows that a_{s}(2s + 5) = a_{s}(2s + 6) = 3. But for these values of n, h_{s}(n) = 3 by (1.4). Finally, the label 2s + 7 is assigned to the second (and last) leaf in S_{2}, so once again applying the above recursion we get h_{s}(2s+7) = 4 = a_{s}(2s+7). See Figure 2.3.

We prove the assertion for n assuming the assertion is true for the first n − 1 entries, where v_{s}(n) is not a node of the 2nd complete partial graph (i.e., n > 2s + 7).

Case 1 : Node v_{s}(n) is a level 0 node, i.e., a super-node. Assume v_{s}(n) = s_{i}, i ≥ 3. By Lemma 2.2(a), we have a_{s}(n) = 2^{i−1}. We will prove that a_{s}(n − s − a_{s}(n − 1)) = a_{s}(n − 2 − s − a_{s}(n − 3)) = 2^{i−2}, from which it follows that a_{s}(n) = 2^{i−1} = a_{s}(n − s − a_{s}(n − 1)) + a_{s}(n − 2 − s − a_{s}(n − 3)).

By the induction assumption a_{s}(n − 1) = h_{s}(n − 1) and a_{s}(n − 3) = h_{s}(n − 3). Thus, a_{s}(n−s−a_{s}(n−1)) = a_{s}(n−s−h_{s}(n−1)) and a_{s}(n−2−s−a_{s}(n−3)) = a_{s}(n−2−s−h_{s}(n−3)). Apply the induction assumption once again to conclude that a_{s}(n − s − h_{s}(n − 1)) = h_{s}(n − s − h_{s}(n − 1)) and a_{s}(n − 2 − s − h_{s}(n − 3)) = h_{s}(n − 2 − s − h_{s}(n − 3)). But by (1.4) h_{s}(n − s − h_{s}(n − 1)) + h_{s}(n − 2 − s − h_{s}(n − 3)) = h_{s}(n), so we get a_{s}(n) = h_{s}(n), as desired.

To complete Case 1, we need to show that a_{s}(n−s−a_{s}(n−1)) = a_{s}(n−2−s−a_{s}(n−3)) = 2^{i−2}. Since v_{s}(n) = s_{i}, we have a_{s}(n − 1) = a_{s}(n) by Lemma 2.1(a). After the chopping process P on T_{s}(n), we get by P3 a new reduced graph with the last node v_{s}(n−s−a_{s}(n)) = s_{i−1}. By Lemma 2.2, a_{s}(n − s − a_{s}(n)) = 2^{i−2}, so a_{s}(n − s − a_{s}(n − 1)) = 2^{i−2}.

If v_{s}(n−2) = s_{i}, let n′ := n−2. Then a_{s}(n−2−s−a_{s}(n−3)) = a_{s}(n′−s−a_{s}(n′−1)) = 2^{i−2}. Otherwise, v_{s}(n − 2) is a level 2 or level 1 node, so by Lemma 2.1, a_{s}(n − 3) = a_{s}(n − 1) − 1. Thus a_{s}(n − 2 − s − a_{s}(n − 3)) = a_{s}(n − 2 − s − a_{s}(n − 1) + 1) = a_{s}(n − 1 − s − a_{s}(n − 1)). But we have already shown that v_{s}(n − s − a_{s}(n)) = v_{s}(n − s − a_{s}(n − 1)) = s_{i−1}, so by Lemmas 2.1 and 2.2, a_{s}(n−1−s−a_{s}(n−1)) = a_{s}(n−s−a_{s}(n−1)) = 2^{i−2}. This completes Case 1.

Case 2 : Node v_{s}(n) is a level 1 node. Assume v_{s}(n) is a node of subtree S_{i} and the rth child of s_{i}, i ≥ 3. By Lemma 2.2(b), we have a_{s}(n) = 2^{i−1} + r − 1. For x ∈ ℝ, let ⌊x⌋ be the floor function of x. We will prove that a_{s}(n − s − a_{s}(n − 1)) = 2^{i−2} + ⌊\frac{r}{2}⌋ and a_{s}(n−2−s−a_{s}(n−3)) = 2^{i−2}+⌊\frac{r−1}{2}⌋, from which it follows that a_{s}(n) = 2^{i−1}+r−1 = a_{s}(n− s−a_{s}(n−1))+a_{s}(n−2−s−a_{s}(n−3)) = h_{s}(n−s−h_{s}(n−1))+h_{s}(n−2−s−h_{s}(n−3)) = h_{s}(n), from the induction assumption as in Case 1.

Since v_{s}(n) is a level 1 node, we have a_{s}(n − 1) = a_{s}(n) by Lemma 2.1(b). After the chopping process P on T_{s}(n), we get by P3 a reduced graph with the last node v_{s}(n − s − a_{s}(n)), the (⌊\frac{r}{2}⌋+1)st child (r odd) of s_{i−1} or the leaf whose parent is the ⌊\frac{r}{2}⌋th child (r even) of s_{i−1}. By Lemma 2.2, a_{s}(n − s − a_{s}(n)) = 2^{i−2} + ⌊\frac{r}{2}⌋, so a_{s}(n − s − a_{s}(n − 1)) = 2^{i−2} + ⌊\frac{r}{2}⌋.

If v_{s}(n − 2) is also a child of s_{i}, then it is the (r − 1)st child. Let n′ := n − 2. Then a_{s}(n − 2 − s − a_{s}(n − 3)) = a_{s}(n′ − s − a_{s}(n′ − 1)) = 2^{i−2} + ⌊\frac{r−1}{2}⌋. Otherwise, r = 1. We have two subcases:

(a) When s > 1, then a_{s}(n) = a_{s}(n−3). After the chopping process P, by P3 the last node of the reduced graph is v_{s}(n−s−a_{s}(n−3)), the first child of s_{i−1}. So v_{s}(n−2−s−a_{s}(n−3)) = s_{i−1}. Thus by Lemma 2.2, a_{s}(n − 2 − s − a_{s}(n − 3)) = 2^{i−2} = 2^{i−2} + ⌊\frac{r−1}{2}⌋.

(b) When s = 0 or 1, then a_{s}(n) = a_{s}(n−3)+1. After the chopping process P, by P3 the last node of the reduced graph is v_{s}(n − s − a_{s}(n)), the first child of s_{i−1}. Thus by Lemma 2.1 and Lemma 2.2, a_{s}(n − 2 − s − a_{s}(n − 3)) = a_{s}(n − s − a_{s}(n) − 1) = a_{s}(n − s − a_{s}(n)) = 2^{i−2} = 2^{i−2} + ⌊\frac{r−1}{2}⌋.

Case 3 : v_{s}(n) is a level 2 node, i.e., a leaf. Assume the parent of v_{s}(n) is the rth child of s_{i}, i ≥ 3. By Lemma 2.2(c), we have a_{s}(n) = 2^{i−1} + r. We will prove that a_{s}(n − s − a_{s}(n − 1)) = 2^{i−2} + ⌊\frac{r+1}{2}⌋ and a_{s}(n − 2 − s − a_{s}(n − 3)) = 2^{i−2} + ⌊\frac{r}{2}⌋, from which it follows that a_{s}(n) = 2^{i−1} + r = a_{s}(n − s − a_{s}(n − 1)) + a_{s}(n − 2 − s − a_{s}(n − 3)) = h_{s}(n − s − h_{s}(n − 1)) + h_{s}(n − 2 − s − h_{s}(n − 3)) = h_{s}(n), from the induction assumption as in Case 1.

Since v_{s}(n) is a level 2 node, we have a_{s}(n − 1) = a_{s}(n) − 1 by Lemma 2.1(c). After the chopping process P on T_{s}(n), we get by P3 a reduced graph with the last node a_{s}(n − s − a_{s}(n − 1)) the (⌊\frac{r}{2}⌋ + 1)st child of s_{i−1} or the leaf whose parent is the ⌊\frac{r}{2}⌋th child of s_{i−1}. By Lemma 2.2, a_{s}(n − s − a_{s}(n) + 1) = 2^{i−2} + ⌊\frac{r+1}{2}⌋, so a_{s}(n − s − a_{s}(n − 1)) = 2^{i−2} + ⌊\frac{r+1}{2}⌋.

If v_{s}(n − 2) is also a node of S_{i}, then it is the child of the (r − 1)st child of s_{i}. Let n′ := n − 2. Then a_{s}(n − 2 − s − a_{s}(n − 3)) = a_{s}(n′ − s − a_{s}(n′ − 1)) = 2^{i−2} + ⌊\frac{r}{2}⌋. Otherwise, r = 1. We have two subcases:

(a) When s > 0, then a_{s}(n) = a_{s}(n−3). After the chopping process P, by P3 the last node of the reduced graph is v_{s}(n−s−a_{s}(n)), the first child of s_{i−1}. So v_{s}(n−s−a_{s}(n)−1) = s_{i−1}. Thus by Lemma 2.1 and Lemma 2.2, a_{s}(n − s − a_{s}(n − 3) − 2) = a_{s}(n − s − a_{s}(n) − 2) = a_{s}(n − s − a_{s}(n) − 1) = 2^{i−2} = 2^{i−2} + ⌊\frac{r}{2}⌋.

(b) When s = 0, then a_{s}(n) = a_{s}(n − 3) + 1. After the chopping process P, by P3 the last node of the reduced tree is v_{s}(n − s − a_{s}(n)), the first child of s_{i−1}. Thus by Lemma 2.1 and Lemma 2.2, a_{s}(n − 2 − s − a_{s}(n − 3)) = a_{s}(n − s − a_{s}(n) − 1) = a_{s}(n − s − a_{s}(n)) = 2^{i−2} = 2^{i−2} + ⌊\frac{r}{2}⌋.

This completes the proof.

From Theorem 2.3, Lemma 2.1 and the definition of a_{s}(n) the following result is immediate .

Corollary 2.4. For every s ≥ 0, the sequence h_{s}(n) is slowly growing. The sequence hits every positive integer twice except for the powers of 2; the number of repetitions of 2^{r}, r ≥ 0, in the sequence h_{s}(n) is s + 2.

For s = 0 it is evident from the definition of a_{0}(n) and Theorem 2.3 that h_{0}(n) = ⌈\frac{n}{2}⌉, which provides a simple closed form for h_{0}(n). This formula is immediate from a casual inspection of Table 1.1, and also follows directly from Corollary 2.4.

Observe that Corollary 2.4 implies that 2^{k} + sk is the index of the last term in h_{s}(n) that equals 2^{k−1}. The argument for this is as follows: there are k powers of 2 less than or equal to 2^{k−1}, each of which occurs s + 2 times in h_{s}(n) while each of the other 2^{k−1} − k positive integers less than or equal to 2^{k−1} occurs twice. But since 2(2^{k−1} − k) + (s + 2)k = 2^{k} + sk we can write h_{s}(n) in terms of h_{0}(n). Since we have a closed form for h_{0}(n) this provides a “piecewise” closed formula for h_{s}(n) where s ≥ 1:

h_{s}(n) = \{ \begin{matrix}h_{0}(n − sk) & 2^{k} + sk ≤ n < 2^{k+1} + sk \\ 2^{k} & 2^{k+1} + sk ≤ n < 2^{k+1} + s(k + 1) \end{matrix}  (2.3)

In a surprising twist it turns out that the sequence h_{1}(n) also has an explicit closed form. This sequence, with the additional initial term h_{1}(0) = 1, appears in [9] as entry \underline{A109964} (Bottomley’s sequence), though the latter is generated by a very different recursion that is not self-referencing. To prove that the two sequences are the same it is enough to show that for n > 0 Bottomley’s sequence satisfies Corollary 2.4. This follows from a straightforward induction; we omit the details. Thus, for n > 0 h_{1}(n) satisfies the recursion in [9] for A109964(n), namely, h_{1}(n) = ⌊\sqrt{∑_{j=0}^{n−1} h_{1}(j)}⌋.

Further, from [9] we have that for n > 0 A109964(n) = ⌊\sqrt{b(n − 1)}⌋ where b(n) is defined by the recursion b(n) = b(n − 1) + ⌊\sqrt{b(n − 1)}⌋, with b(0) = 1. But in [5, Chap. 3, Exer.

3.28], the following closed form for b(n) is attributed to Carl Witty:

b(n − 1) = 2^{k} + ⌊(\frac{n − k}{2} )^{2}⌋, 2^{k} + k ≤ n < 2^{k+1} + k + 1.

Thus we have the following closed form for h_{1}(n):

h_{1}(n) = ⌊\sqrt{2^{k} + ⌊(\frac{n − k}{2} )^{2}⌋}⌋, 2^{k} + sk ≤ n ≤ 2^{k+1} + sk.

For s > 1 there does not seem to be any comparable closed form for h_{s}(n).

Note that it is possible to generate the family of sequences h_{s}(n) from a slightly different infinite tree graph and a modified numbering scheme for the nodes.

Figure 2.6: The initial portion of T′_{s} with s = 2.

The new tree structure T′_{s} is our original T_{s} minus the isolated node I. We label each node with integers 1, 2, 3, ⋯ as follows: All subtrees, starting with S_{1}, are labelled consecutively with the smallest labels not yet used. For each subtree S_{i}, first label the leaf of the first child of super-node s_{i} and then label the first child of s_{i}, each node receiving one label. Next, label the super-node s_{i} with s consecutive labels not yet used, where s is the parameter of the sequence h_{s}(s). Now label each of the remaining level 2 and level 1 nodes of the subtree S_{i} with a single label in increasing order first from level 2 to level 1 nodes and then from left to right. See Figure 2.6, where we show the initial portion of T′_{s} for s = 2. If we define the chopping process in the same way as before, with the obvious modification since we no longer have an isolated node, then it is easy to see that the sequence h_{s}(n) can be interpreted in terms of the leaves in the this new graph T′_{s}.

3 Generating Function

We compute a generating function for {a_{s}(n)}_{n=1}^{∞}, which is also the generating function for {h_{s}(n)}_{n=1}^{∞} by Theorem 2.3. Define A_{s}(z) := ∑_{k=1}^{∞} a_{s}(k)z^{k} and D_{s}(z) := ∑_{k=1}^{∞} d_{s}(k)z^{k}. By (2.1), we know that A_{s}(z) = \frac{D_{s}(z)}{1−z}. So it’s enough to find D_{s}(z). From the definition of d_{s}(n) it is clear that the subsequence of the sequence d_{s}(n) corresponding to S_{i}, i > 0, is of the form 0^{s}01 ⋯ 01, with 2^{i−1} consecutive 01’s, preceded by s consecutive 0’s, denoted by 0^{s}. Thus {d_{s}(n)}_{n=1}^{∞} is 1⋮0^{s}01⋮0^{s}0101⋮0^{s}01010101⋮ ⋯

For n > 1, define the concatenation C_{n} = C_{n−1}C_{n−1}, with C_{0} = 1 and C_{1} = 01. Let C_{n}(k) be the kth entry of C_{n}. It is obvious that {d_{s}(n)}_{n=1}^{∞} can be written as C_{0}0^{s}C_{1}0^{s}C_{2}0^{s}C_{3}0^{s} · · ·. Further we have

Lemma 3.1. The length of C_{n} is |C_{n}| = 2^{n} and for n > 0,

C_{n}(z) := ∑_{k=1}^{2^{n}} C_{n}(k)z^{k} = ∑_{i=1}^{2^{n−1}} z^{2i} = \frac{z^{2}}{1 − z^{2}} (1 − z^{2^{n}}).

Proof. Evidently |C_{0}| = 1 and for n > 0, C_{n} has 2^{n−1} pairs of 01, so |C_{n}| = 2^{n}. Each 1 occurs as the second entry in every pair, so the result follows.

Theorem 3.2. The generating function D_{s}(z) is equal to

z + \frac{z^{2}}{1 − z^{2}} ∑_{i=1}^{∞} z^{si+2^{i}−1}(1 − z^{2^{i}})

Proof.

D_{s}(z) = z + ∑_{i=1}^{∞} z^{si+∑_{j=0}^{i−1} |C_{j}|}C_{i}(z)

= z + ∑_{i=1}^{∞} z^{si+2^{i}−1} \frac{z^{2}}{1 − z^{2}} (1 − z^{2^{i}})

= z + \frac{z^{2}}{1 − z^{2}} ∑_{i=1}^{∞} z^{si+2^{i}−1}(1 − z^{2^{i}})

Remark. We can also rewrite the expression for D_{s}(z)

D_{s}(z) = z + \frac{z^{2}}{1 − z^{2}} ∑_{i=1}^{∞} z^{si+2^{i}−1}(1 − z^{2^{i}})

= z + \frac{z^{2}}{1 − z^{2}} z^{s+2^{0}}[1 − z^{2^{1}} + z^{s+2^{1}}[1 − z^{2^{2}} + z^{s+2^{2}}[1 − z^{2^{3}} + z^{s+2^{3}}[⋯

= \frac{z^{2}}{1 − z^{2}} [\frac{1}{z} − z^{2^{0}} + z^{s+2^{0}}[1 − z^{2^{1}} + z^{s+2^{1}}[1 − z^{2^{2}} + z^{s+2^{2}}[1 − z^{2^{3}} + z^{s+2^{3}} ⋯

Corollary 3.3. The generating function A_{s}(z) is equal to

\frac{z}{1 − z} + \frac{z^{2}}{(1 − z^{2})(1 − z)} ∑_{i=1}^{∞} z^{si+2^{i}−1}(1 − z^{2^{i}})

Proof. By the proposition and A_{s}(z) = \frac{D_{s}(z)}{1−z}.

4 Concluding Remark

It is equally natural to investigate the meta-Fibonacci recursion that derives from the odd values of the index on the right hand side of (1.2), that is,

g_{s,k}(n) = ∑_{j=0}^{k−1} g_{s,k}(n − (2j + 1) − s − g_{s,k}(n − (2j + 2))),  n > s + 2k.  (4.1)

For general k and s, the recursion (4.1) produces a much richer collection of infinite sequences (that is, sequences that do not die) for various sets of initial conditions. In many instances these sequences exhibit considerably more complicated behavior than h_{s}(n). To date we have not been able to discover a combinatorial interpretation for any of these sequences, whose behavior will be the subject of a future communication.

Acknowledgements

The authors are grateful to Rafel Drabek, Noah Cai and Junmin Park for research assistance at various early stages of this work, and to an anonymous referee for several helpful observations.

References

[1] J. Callaghan, J. J. Chew III and S. M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM J. Discrete Math., 18 (2005), 794-824.

[2] B. W. Conolly, Meta-Fibonacci sequences, in S. Vajda, ed., Fibonacci & Lucas Numbers, and the Golden Section, Wiley, New York, 1986, pp. 127-137.

[3] C. Deugau and F. Ruskey, Complete k-ary trees and generalized meta-Fibonacci sequences, Fourth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings Series, 2006 AG, pp. 203-214.

[4] C. Elzinga, private communication, October 2001.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Second Edition, Addision-Wesley, Massachusetts, 1994, pp. 97, 509.

[6] J. Higham and S. M. Tanny, More well-behaved meta-Fibonacci sequences, Congr. Numer., 98 (1993), 3-17.

[7] B. Jackson and F. Ruskey, Meta-Fibonacci sequences, binary trees and extremal compact codes, Electron. J. Combin., 13 (2006), R26, 13 pages.

[8] F. Ruskey, private communication, August 2007.

[9] N. J. A. Sloane, Online Encyclopedia of Integer Sequences,

    http://www.research.att.com/∼njas/sequences.

[10] S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Math. 105 (1992), 227-239.

2000 Mathematics Subject Classification: Primary 05A15. Secondary 11B37; 11B39. Keywords: meta-Fibonacci recursion; Hofstadter sequence.

(Concerned with sequences \underline{A008619}, \underline{A109964}.)

Received January 4 2008; revised version received May 22 2008. Published in Journal of Integer Sequences, May 23 2008.

Return to Journal of Integer Sequences home page.