ON THE BEHAVIOUR OF A FAMILY

OF META-FIBONACCI SEQUENCES

Joseph Callaghan, John J. Chew, III and Stephen M. Tanny

July 26th, 2004 (initially submitted January 13, 2003) (2nd version)

Abstract. A family of meta-Fibonacci sequences is defined by the k-term recursion

T_{a,k}(n) := ∑_{i=0}^{k−1} T_{a,k}(n − i − a − T_{a,k}(n − i − 1)), n > a + k, k ≥ 2.

with initial conditions T_{a,k}(n) = 1 for 1 ≤ n ≤ a + k. Some partial results are obtained for a ≥ 0 and k > 1. The case a = 0 and k odd is analyzed in detail giving a complete characterization of its structure and behaviour, marking the first time that such a parametric family of meta-Fibonacci sequences has been solved. This behaviour is considerably more complex than that of the more familiar Conolly sequence (a = 0, k = 2). Various properties are derived: for example, a certain difference of summands turns out to consist of palindromic subsequences, and the mean values of the functions on these subsequences are computed. Conjectures are made concerning the still more complex behaviour of a = 0 and even k > 2.

1. Introduction

In this paper, all values are integers and defining equations use the ‘:=’ operator. For a sequence T and an integer d, we write Δ_{d}T (n) := T (n) − T (n − d).

Hofstadter’s Q-sequence Q(n), illustrated in Figure 1.1, first mentioned in [7] and defined by the “self-referencing” recursion

(1.1)  Q(n) := Q(n − Q(n − 1)) + Q(n − Q(n − 2)), n > 2

and initial conditions Q(1) := Q(2) := 1 is the most famous example of a so-called meta-Fibonacci sequence. This sequence, recently renamed U(n) by Hofstadter and his collaborators [9], remains the focus of ongoing investigation in [8] and elsewhere, although to date very little has been proven about its enigmatic behaviour.

At the same time, various authors have examined seemingly close relatives to the above recursion, which have turned out to be far better behaved and about which a great deal can be demonstrated. In [3], B.W. Conolly introduced the following very well-behaved variant of the Q-sequence recursion, illustrated in Figure 1.2:

(1.2)  F (n) := F (n − F (n − 1)) + F (n − 1 − F (n − 2)), n > 2

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11B37, 11B39, 11B99.

Key words and phrases. Hofstadter, iterated recursion, meta-Fibonacci, Q-sequence.

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}Q(n) \\ 1 \\ 1 \\ 2 \\ 3 \\ 3 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 6 \\ 8 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}Q(n) \\ 8 \\ 8 \\ 10 \\ 9 \\ 10 \\ 11 \\ 11 \\ 12 \\ 12 \\ 12 \\ 12 \\ 16 \end{matrix} 0
0  50  100  150  200

Figure 1.1: Hofstadter’s Q Sequence

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}F (n) \\ 1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 4 \\ 4 \\ 4 \\ 5 \\ 6 \\ 6 \\ 7 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}F (n) \\ 8 \\ 8 \\ 8 \\ 8 \\ 9 \\ 10 \\ 10 \\ 11 \\ 12 \\ 12 \\ 12 \\ 13 \end{matrix} 0
0  50  100  150  200

Figure 1.2: Conolly’s F Sequence

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.

Much can be said about this sequence. For example, Conolly shows that if F (1) = 0 and n = 2^{i} + j with i ≥ 1 and 0 ≤ j < 2^{i}, then

(1.3)  F (n) = 2^{i−1} + F (j + 1)

Tanny [14] and Higham and Tanny [5, 6] developed a considerably more extensive analysis of the very similar recursion, illustrated in Figure 1.3, defined by:

(1.4)  T (n) := T (n − 1 − T (n − 1)) + T (n − 2 − T (n − 2)), n > 2

with initial conditions T (0) := T (1) := T (2) := 1, which generates a sequence with highly analogous properties. Detailed results were provided concerning the structure and behaviour of this sequence, and of some other sequences generated by Equation (1.4) but with alternative choices for the initial conditions.

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}T (n) \\ 1 \\ 1 \\ 2 \\ 2 \\ 2 \\ 3 \\ 4 \\ 4 \\ 4 \\ 4 \\ 5 \\ 6 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}T (n) \\ 6 \\ 7 \\ 8 \\ 8 \\ 8 \\ 8 \\ 8 \\ 9 \\ 10 \\ 10 \\ 11 \\ 12 \end{matrix} 0
0  50  100  150  200

Figure 1.3: Tanny’s T Sequence

In [5], a k-term generalization of Equation (1.4) was suggested:

(1.5)  T_{k}(n) := ∑_{i=1}^{k} T_{k}(n − i − T_{k}(n − i)), n > k

It was proven there that with the initial conditions T_{k}(0) := T_{k}(1) := 1 and T_{k}(i) := i − 1, 2 ≤ i ≤ k, the sequence generated by Equation (1.5) behaves in very much the same way as the sequence generated by Equation (1.4) with initial conditions T (0) := T (1) := T (2) := 1. That is, it is monotone, its consecutive terms increase by either 0 or 1, and it hits every positive integer. Further, we can determine explicit formulae that characterize its behaviour.

The work cited above with Equation (1.5) demonstrates that recursions expressible as homogeneous sums may be approachable even when the sums have many terms. Motivated by this success, we introduce an even more general formulation of the Conolly recursion (1.2) that incorporates all of the specific variants discussed above.

For a ≥ 0 and k ≥ 2 consider the family of recursions

(1.6)  T_{a,k}(n) := ∑_{i=0}^{k−1} T_{a,k}(n − i − a − T_{a,k}(n − i − 1)), n > a + k.

Equation (1.6) reduces to Equation (1.2) when a = 0 and k = 2, to Equation (1.4) when a = 1 and k = 2, and to Equation (1.5) when a = 1. For k = 2 and arbitrary (even negative) a, Elzinga [4] reports that some analogues of certain results of Equation (1.5) appear to hold, although no proof is provided; again, for k = 2 and a ∈ { −1, −2 }, he describes the behaviour of Equation (1.6) for a substantial number of sets of initial conditions in an attempt to identify a behavioural classification scheme. For k = 3 and a = 0, Allenby and Smith [1] present some initial results and conjectures.

As is typical for meta-Fibonacci recursions, the behaviour of the individual members of this family is highly sensitive to the choice of the parameters a and k, and to

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}T (n) \\ 0 \\ 0 \\ 2 \\ 2 \\ 4 \\ 2 \\ 6 \\ 4 \\ 8 \\ 4 \\ 10 \\ 6 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}T (n) \\ 12 \\ 6 \\ 14 \\ 8 \\ 16 \\ 8 \\ 18 \\ 10 \\ 20 \\ 10 \\ 22 \\ 12 \end{matrix} 0
0  50  100  150  200

Figure 1.4: T_{0,3} with initial values (0, 0, 2)

the initial conditions. Some choices lead to sequences with identifiable and regular (though potentially very complex) patterns, while others generate highly chaotic sequences or even cause the sequence T_{a,k}(n) to fail to be defined for some n.

For example, consider the choice of initial values for the sequence T_{0,3}. If we require that each of the three summands that make up the recursive definition (1.6) of T_{0,3}(4) evaluates to one of the chosen initial values, then the three conditions 1 ≤ 4−i−T_{0,3}(3−i) ≤ 3, i ∈ {1, 2, 3} allow 27 possible sets of initial values ranging lexicographically from (T_{0,3}(1), T_{0,3}(2), T_{0,3}(3)) = (−1, 0, 1) to (1, 2, 3). Four of the 27 choices — (−1, 0, 2), (−1, 0, 3), (−1, 2, 3) and (1, 0, 3) — give a T_{0,3}(n) which is not well-defined for some 5 ≤ n ≤ 7. In the other 23 cases, we have verified empirically that T_{0,3}(n) is defined at least up to n = 10, 000.

Four of the remaining 23 cases — (0, 0, 2), (0, 0, 1), (1, 1, 1), and (−1, 0, 1) — are graphed and tabulated in Figures 1.4, 1.5, 1.6 and 1.7, and illustrate the wide range of possible behaviour for these sequences. Observe that the first and third sequences visibly bifurcate into an even subsequence and an odd subsequence, each of which is monotonic even though the full sequence is not. The second sequence appears to be very similar to Conolly’s sequence, while the fourth sequence looks completely chaotic.

It is also typical of meta-Fibonacci recursions that alternative choices for the parameters and initial conditions can lead to essentially the same sequence. In this vein, it is not difficult to show that if T (n) is always well-defined and positive, and some other T^{∗}(n) defined according to Equation (1.6) satisfies T^{∗}(N + p) = T (p) for an N ≥ 0 and 1 ≤ p ≤ a + k, then T^{∗}(N + p) = T (p) for all p ≥ 1. For instance, setting a = 0, k = 3 and {T (n)}_{n=1,2,3} = (−1, 1, 2) or (1, 1, 1) gives two sequences that are identical except that one has four extra values at its start. We also note that we may replace n by n′ + x in Equation (1.6) to shift a sequence x places.

In this paper, we analyse the general family defined by Equation (1.6) and initial conditions T_{a,k}(n) = 1 for 1 ≤ n ≤ a+k. We choose this set of initial values because as shown in Figure 1.6, its bifurcated, undulating behaviour is complex enough to be interesting, while still structured enough to be amenable to rigorous analysis.

In Section 2 we prove that for general a, the sequence generated by each recursion in the family can be decomposed into k disjoint subsequences, each of which begins

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}T (n) \\ 0 \\ 0 \\ 1 \\ 2 \\ 3 \\ 3 \\ 4 \\ 5 \\ 6 \\ 6 \\ 7 \\ 8 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}T (n) \\ 9 \\ 9 \\ 9 \\ 10 \\ 11 \\ 12 \\ 12 \\ 13 \\ 14 \\ 15 \\ 15 \\ 16 \end{matrix} 0
0  50  100  150  200

Figure 1.5: T_{0,3} with initial values (0, 0, 1)

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}T (n) \\ 1 \\ 1 \\ 1 \\ 3 \\ 3 \\ 3 \\ 5 \\ 5 \\ 7 \\ 5 \\ 7 \\ 7 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}T (n) \\ 9 \\ 9 \\ 9 \\ 11 \\ 11 \\ 13 \\ 11 \\ 15 \\ 13 \\ 17 \\ 13 \\ 17 \end{matrix} 0
0  50  100  150  200

Figure 1.6: T_{0,3} with initial values (1, 1, 1)

with 1 and increases monotonically in increments of 0 or k − 1. Further, for all odd k, the differences T_{a,k}(n)−T_{a,k}(n−2) are also always either 0 or k −1. This finding substantially generalizes an earlier result of this type for Equation (1.4) appearing in Higham and Tanny [5, 6].

In Sections 3 and 4, we apply and extend the results of Section 2 to derive a detailed characterization of the behaviour of Equation (1.6) in the special case a = 0, k = 3, and explore the many interesting properties and beautiful symmetries that it exhibits. This case illustrates well the additional complexity that occurs once k is increased beyond 2, yet remains manageable for expository purposes. In the course of our work, we considerably extend the results on this case that appear in [1] and settle all the conjectures stated there.

While the case a = 0, k = 3 is interesting in its own right, what is more exciting is that the behaviour in this case appears to provide a roadmap for understanding and characterizing the detailed behaviour of the sequences for all odd k. This is the content of Section 5, where we prove that certain key results derived for a = 0,

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}T (n) \\ -1 \\ 0 \\ 1 \\ 3 \\ 2 \\ 4 \\ 4 \\ 7 \\ 4 \\ 7 \\ 7 \\ 9 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}T (n) \\ 8 \\ 9 \\ 11 \\ 10 \\ 10 \\ 13 \\ 15 \\ 13 \\ 13 \\ 13 \\ 18 \\ 15 \end{matrix} 0
0  50  100  150  200

Figure 1.7: T_{0,3} with initial values (−1, 0, 1)

k = 3 hold for all odd k. On this basis, we show that the detailed structure for all odd k is analogous to that shown for k = 3. To the best of our knowledge, this is the first instance in the area of meta-Fibonacci recursions where such broadlybased behavioural results have been shown to hold for sequences with such complex behaviour.

For even k ≥ 4 the behaviour of T (n) is much more complicated and erratic than for odd k (the case k = 2, the Conolly sequence discussed earlier, is completely understood and quite straightforward). There is evidence that the same kind of approaches that we used for odd k can be adapted for even k, although we have not yet investigated this very far. In Section 6, we conclude with some conjectures relating to even k.

2. A Family of Meta-Fibonacci Sequences

In this section, we prove some results concerning the general recursion

(1.6)  T_{a,k}(n) := ∑_{i=0}^{k−1} T_{a,k}(n − i − a − T_{a,k}(n − i − 1)), n > a + k.
(2.1)  T_{a,k}(n) := 1, 1 ≤ n ≤ k + a

which for brevity’s sake we will refer to simply as T (n).

Table 2.1 lists some values of T (n) for the case a = 0, k = 7, and lets us observe a few of its properties: T (n) ≡ 1 (mod k−1); T (n) is not monotonic but is composed of k − 1 interleaved monotonic subsequences {T ((k − 1)i + j)}_{i=0}^{∞}, j = 1,…, k − 1; and each of these subsequences includes every possible value subject to the modulo constraint. That is, Δ_{k−1}T (n) := T (n) − T (n − k + 1) ∈ { 0, k − 1 } for all n ≥ k. Furthermore, in the case of odd k, we will find that Δ_{d}T (n) := T (n) − T (n − d) ∈ { 0, k − 1 } for all even d ∈ [0, k − 1].

We begin our analysis of T (n). In the case of an ordinary Fibonacci sequence, the recursive definition of a sequence member refers simply to immediately preceding sequence members. In the meta-Fibonacci sequence T (n), the recursive summands are usually much earlier sequence members, whose distance from the current n can

n  n
1 2 3 4 5 6  1 2 3 4 5 6
T (n + 0) 1 1 1 1 1 1 T (n + 60) 49 49 49 55 55 55
T (n + 6) 1 7 7 7 7 7 T (n + 66) 55 55 55 61 55 61
T (n + 12) 7 7 13 13 13 13 T (n + 72) 61 61 61 67 61 67
T (n + 18) 13 13 19 13 19 19 T (n + 78) 61 67 67 73 67 73
T (n + 24) 19 19 25 19 25 19 T (n + 84) 67 73 67 79 73 79
T (n + 30) 25 25 31 25 31 25 T (n + 90) 73 79 73 85 73 85
T (n + 36) 31 25 31 31 37 31 T (n + 96) 79 85 79 91 79 91
T (n + 42) 37 31 37 37 37 37 T (n + 102) 79 91 85 97 85 97
T (n + 48) 43 37 43 43 43 43 T (n + 108) 85 97 85 103 91 103
T (n + 54) 43 43 49 49 49 49 T (n + 114) 91 103 91 109 91 109

Table 2.1: T_{0,7}(n)

n  n
1 2 3 4 5 6  1 2 3 4 5 6
U(n + 0) − 1 1 1 1 1 U(n + 60) 7 7 7 13 7 7
U(n + 6) 1 1 1 1 1 1 U(n + 66) 7 7 7 13 7 13
U(n + 12) 1 1 7 1 1 1 U(n + 72) 7 7 7 13 7 13
U(n + 18) 1 1 7 1 7 1 U(n + 78) 7 13 7 13 7 13
U(n + 24) 1 1 7 1 7 1 U(n + 84) 7 13 7 19 7 13
U(n + 30) 7 1 7 1 7 1 U(n + 90) 7 13 7 19 7 19
U(n + 36) 7 1 7 7 7 1 U(n + 96) 7 13 7 19 7 19
U(n + 42) 7 1 7 7 7 7 U(n + 102) 7 19 7 19 7 19
U(n + 48) 7 1 7 7 7 7 U(n + 108) 7 19 7 25 7 19
U(n + 54) 7 7 7 7 7 7 U(n + 114) 7 19 7 25 7 25

Table 2.2: U_{0,7}(n)

vary considerably within the sum. We therefore need to examine these summands more closely, and reword the definition (1.6) of T_{a,k}(n) to label two functions of subsequent interest:

(2.2)  T_{a,k}(n) = ∑_{i=0}^{k−1} U_{a,k}(n − i), n > a + k.

where

U_{a,k}(n) := T_{a,k}(R_{a,k}(n)), n > a + 1
R_{a,k}(n) := n − a − T_{a,k}(n − 1), n > 1.

n  n
1 2 3 4 5 6  1 2 3 4 5 6
R(n + 0) − 1 2 3 4 5 R(n + 60) 12 13 14 15 10 11
R(n + 6) 6 7 2 3 4 5 R(n + 66) 12 13 14 15 10 17
R(n + 12) 6 7 8 3 4 5 R(n + 72) 12 13 14 15 10 17
R(n + 18) 6 7 8 3 10 5 R(n + 78) 12 19 14 15 10 17
R(n + 24) 6 7 8 3 10 5 R(n + 84) 12 19 14 21 10 17
R(n + 30) 12 7 8 3 10 5 R(n + 90) 12 19 14 21 10 23
R(n + 36) 12 7 14 9 10 5 R(n + 96) 12 19 14 21 10 23
R(n + 42) 12 7 14 9 10 11 R(n + 102) 12 25 14 21 10 23
R(n + 48) 12 7 14 9 10 11 R(n + 108) 12 25 14 27 10 23
R(n + 54) 12 13 14 9 10 11 R(n + 114) 12 25 14 27 10 29

Table 2.3: R_{0,7}(n)

As with T (n), we abbreviate U_{a,k}(n) to U(n) and R_{a,k}(n) to R(n) wherever the understood subscripts are clear. Returning to the case a = 0, k = 7, Table 2.2 lists the first 119 values of U(n) and shows that it has the same modulo and subsequence properties that T (n) has, that is, Δ_{k−1}U(n) takes on only the two values 0 and k − 1.^{1} Table 2.3 lists the first 119 values of R(n), which also shares all of these properties with T (n) and U(n).

Note 2.1. We can make a stronger observation for Δ_{6}U(n) that turns out to generalize to any k: every pair of 6’s in this difference sequence appears to be separated by at least 7 zeroes. The following are the first 88 values of Δ_{6}U(n), listed with a break before each 6: {Δ_{6}U(n)}_{n=8}^{95} = { 0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0, 0,0,0,0,0, 6,0,0,0,0,0,0,0, 6,0,0,0,0,0,0,0 }.

Since Δ_{k−1}T (n) = ∑_{i=0}^{k−1} Δ_{k−1}U(n − i), it follows that if we can fully describe Δ_{k−1}U(n), then we have described its double sum T (n). In fact we will demonstrate that, as is illustrated in Note 2.1, Δ_{k−1}U(n) has a beautiful, highly regular structure for general k from which many properties of Δ_{k−1}T (n) and hence T (n) can readily be deduced. For example, if Note 2.1 is generally true for k = 7, then Δ_{6}T (n) also takes on only the values 0 and 6. We may thus conclude that (unlike many meta-Fibonacci sequences) T (n) is well-defined for all n.

We now show that this is true for general k.

Proposition 2.2. The following differences are all either 0 or k − 1: Δ_{k−1}T (n) for n ≥ k, Δ_{k−1}R(n) for n > k and Δ_{k−1}U(n) for n > k + a. As a result, the following sequence values are all (well) defined: T (n) for n > 0, R(n) for n > 1 and U(n) for n > a + 1.

Proof. We begin an inductive proof by verifying that the proposition holds for n ≤ 2k + a.

1Δ_{2}U_{0,3}(n) is what Allenby and Smith [1] call a pairing, though they neither explicitly define the sequence {Δ_{2}U_{0,3}(n)} nor make it the focus of their analysis as we do here.

T (n) = 1 for 1 ≤ n ≤ k + a by (2.1). It is easy to compute using equations (1.6) and (2.1) that T (n) = k for k + a < n ≤ 2k + a. Δ_{k−1}T (n) is thus either 0 or k − 1 for k ≤ n ≤ 2k + a.

R(n) := n − a − T (n − 1) is n − a − 1 for 2 ≤ n ≤ k + a + 1 and is n − a − k > 0 for k + a + 1 < n ≤ 2k + a + 1. Δ_{k−1}R(n) = k − 1 − Δ_{k−1}T (n − 1) is either 0 or k − 1 for k + 1 ≤ n ≤ 2k + a + 1.

U(n) := T (R(n)). When k + a + 1 ≤ n ≤ 2k + a, we have 1 ≤ R(n) ≤ k, When 1 ≤ k ≤ n, we have T (n) = 1. So when k + a + 1 ≤ n ≤ 2k + a, we have U(n) = T (R(n)) = 1. Thus, Δ_{k−1}U(n) = 0 is for k + a + 1 ≤ n ≤ 2k + a.

Now let n > 2k + a and proceed assuming that the proposition holds for all lesser n.

R(n) := n − a − T (n − 1) is defined.

Δ_{k−1}R(n) = k − 1 − Δ_{k−1}T (n − 1) is either k − 1 or 0, since Δ_{k−1}T (n − 1) is either 0 or k − 1.

U(n) := T (R(n)). To confirm that U(n) is well defined, we need to show that R(n) is well-defined (which we just did), and that T is well defined at R(n). That is, we require that 0 < R(n) < n. Let m ∈ [k+a+2, 2k+a+1] with m ≡ n (mod k−1). Then R(n) = R(m) + Δ_{k−1}R(m + k − 1) + Δ_{k−1}R(m + 2(k − 1)) + … + Δ_{k−1}R(n). The first summand is positive and the rest are all either 0 or k − 1, so R(n) is positive. Likewise, T (n) > 0, so R(n) := n − a − T (n − 1) < n. Therefore, we can apply induction to find that U(n) is defined.

Δ_{k−1}U(n) = T (R(n)) − T (R(n − k + 1)). We just showed that R(n) − R(n − k + 1) = Δ_{k−1}R(n) is either 0 or k − 1. If this difference is zero, then so is Δ_{k−1}U(n). If it’s k − 1, then Δ_{k−1}U(n) = (Δ_{k−1}T)(R(n)), which is 0 or k − 1 by the induction assumption.

From Equation (2.2), we have T (n) = T (n − 1) + U(n) − U(n − k), so T (n) is well-defined.

Δ_{k−1}T (n) = ∑_{i=0}^{k−1} Δ_{k−1}U(n − i) from Equation (2.2) and the linearity of the difference operator. If all the summands are zero, then so is Δ_{k−1}T (n) and we are done. If not, let j be the largest integer in [n − k + 1, n] for which k − 1 = Δ_{k−1}U(j) = T (R(j)) − T (R(j − k + 1)). Then Δ_{k−1}R(j) = k − 1 and 0 = k − 1 − Δ_{k−1}R(j) = Δ_{k−1}T (j − 1) = ∑_{i=0}^{k−1} Δ_{k−1}U(j − 1 − i). Therefore at most one of Δ_{k−1}U(n − k + 1), …, Δ_{k−1}U(n) can have the value k − 1 while the others must be zero, so their sum Δ_{k−1}T (n) is either 0 or k − 1. □

Note that other choices of initial values for T will prevent the initial conditions of the induction from being satisfied, and that in such cases Δ_{k−1}U(n) and Δ_{k−1}T (n) may belong to a larger finite set (see Figure 1.4, or the case a = 0, k = 3 with initial values {0, 2, 1}) or take on an infinite number of different values (see Figure 1.7).

Corollary 2.3. For n > 2k + a + 1, if Δ_{k−1}T (n) = 0 then Δ_{k−1}U(n − k + 1) = Δ_{k−1}U(n − k + 2) = … = Δ_{k−1}U(n) = 0.

Proof. If 0 = Δ_{k−1}T (n) = ∑_{j=0}^{k−1} Δ_{k−1}U(n − j) and each summand is either 0 or k − 1, each summand must be zero. □

Corollary 2.4. For each j in [1, k], the subsequence {T ((k − 1)i + j)}_{i=0}^{∞} begins with 1 and increases monotonically in increments of 0 or k − 1.

Proof. The result follows immediately from the initial conditions for T and what we have shown about the differences Δ_{k−1}T (n). □

Corollary 2.5. In the sequence Δ_{k−1}U(n), n > a + k, there are at least k zeroes between each pair of nonzero values.

Proof. We showed in the proof of Proposition 2.2 that Δ_{k−1}U(n) = 0 for k + a < n ≤ 2k + a and if for some j > 2k + a the jth member of Δ_{k−1}U is nonzero, then it is preceded by at least k zeroes. □

The preceding corollary describes the fine structure of Δ_{k−1}U(n) and helps explain why that sequence attracts our interest. We conclude this section by formally defining the blocks that make up the structure of the Δ_{k−1}U(n) sequence.

Definition 2.6. A p-block is a consecutive subsequence of length p in {Δ_{k−1}U(n)}, consisting of an initial nonzero value together with all of the zeroes which follow it.

Example 2.7. The values of Δ_{6}U(n) listed in Note 2.1 constitute seven zeroes, followed by two 8-blocks, one 9-block, and seven more 8-blocks.

3. The Structure of a Three-Term Recursion

We move now from general observations about properties of our family of difference functions to the specific case k = 3; observe that this is a three-term generalization of Conolly’s sequence (1.2). This case illustrates the increased structural complexity that occurs for k > 2. It also demonstrates concretely the behaviour typical of odd k, to be elaborated in Section 5.^{2}

In Equation (1.6), set a = 0, k = 3 and assume the initial conditions T_{0,3}(n) = 1 for n = 1, 2, 3. For the remainder of this section and in the next section, we refer to this sequence as T (n), to R_{0,3}(n) as R(n), and to U_{0,3}(n) as U(n):

(3.1)  T (n) := U(n) + U(n − 1) + U(n − 2), n > 3
U(n) := T (R(n)), n > 1
R(n) := n − T (n − 1), n > 1

Table 3.1 lists values of T (n), U(n) and R(n) for small n.

Note 3.1. For future reference, we list the following values of {Δ_{2}U(n)}_{n=4}^{97} = { 0, 0,0, 2,0,0,0,0, 2,0,0,0, 2,0,0,0, 2,0,0,0,0, 2,0,0,0,0, 2,0,0,0,0, 2,0,0,0, 2,0,0,0, 2,0,0,0, 2,0,0,0, 2,0,0,0, 2,0,0,0,0, 2,0,0,0,0, 2,0,0,0,0, 2,0,0,0,0, 2,0,0,0, 2,0,0,0,0, 2,0,0,0, 2, 0,0,0,0, 2,0,0,0,0 }.

We completely describe the behaviour of T, as well as the related sequences U and R. As is the case with many other meta-Fibonacci sequences, the T sequence can be naturally decomposed into strings of consecutive terms called generations. The generational structure is clearly visible in Figure 1.6, where the end of each generation is marked by several points of intersection of the two curves. The lengths of the generations increase geometrically, and properties of the sequence recur from generation to generation giving a structure which might be described as logarithmicperiodic.

To describe completely the behaviour of T (n) it is sufficient to characterize fully the behaviour of Δ_{2}U(n), since T (n) can be reconstructed as a double sum of

2Using very different methods, Allenby and Smith [1] analyze this recursion together with several other, less complicated, meta-Fibonacci recursion variants. In this section and the next, we extend considerably the results proven in [1] and settle all the conjectures stated therein.

n  1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
T(n) 1 1 3 5 7 7 9 9 11 11 13 13 15 17 17 19 19 21 23 25
T(n + 1) 1 3 3 5 5 7 9 11 13 15 17 17 19 19 21 23 23 25 25 27
U(n) − 1 1 3 3 3 3 3 3 3 3 3 5 5 5 5 5 7 7 9
U(n + 1) 1 1 1 1 1 3 3 5 5 7 7 7 7 7 9 9 9 9 9 9
R(n) − 2 2 4 4 6 6 6 6 6 6 6 8 8 10 10 10 12 12 14
R(n + 1) 1 3 3 3 3 5 5 7 7 9 9 11 11 11 13 13 15 15 15 15

Table 3.1: T (n), U(n), R(n) for a = 0, k = 3

Δ_{2}U(n). Indeed, the generational structure of T (n) is mirrored in a surprising way in a corresponding generational structure in the Δ_{2}U(n) sequence. Even further, we will show that each of these corresponding generations in Δ_{2}U is in turn made up of substrings we call lines and sub-substrings we call feet. That is, we will show how Δ_{2}U(n) consists of feet, concatenations of which form lines, and how consecutive lines complete the generation. We also show that the feet in each generation in Δ_{2}U(n) are determined by (and in fact are in the one-to-one correspondence shown in Figure 3.4 with) the values of Δ_{2}T in the immediately preceding generation. In this way, the preceding generation of T determines new feet, that make up new lines, that make up a new generation in Δ_{2}U, that determines the new generation of T.

From Note 3.1, we empirically observe (and will show below in Proposition 3.3) that from n = 7 onward Δ_{2}U(n) appears to consist only of 4-blocks and 5-blocks. We will see that the interesting values of n are those which start a 4-block, start a 5-block or end a 5-block, and that it is logical then to look at Δ_{2}U as consisting mostly of subsequences { 2, 0, 0, 0 } with the occasional extra { 0 }.

Perhaps not surprisingly, the ancient Greeks [2, 11] had words for such patterns (feet) of one stressed beat followed by three unstressed beats (a first paeon), for a sequence of such patterns (a line), and for an extra unstressed beat at the end of a sequence (a hypercatalectic). While Greek prosodists were concerned with long and short syllables in poetry and we are dealing with twos and zeroes in an iterated recursion, the analogy is precise, and so we borrow their terminology to define our first type of subsequence.

Definition 3.2 (Foot). A paeon is a sequence { 2,0,0,0 } of consecutive values of Δ_{2}U(n). A hypercatalectic is a singleton sequence { 0 }, immediately preceded in {Δ_{2}U(n)} by a paeon. A foot is either a paeon or a hypercatalectic. For convenience, we will write { P } interchangeably with { 2, 0, 0, 0 } and likewise { H } with { 0 } when listing values of Δ_{2}U. We also define φ(n) as the symbol P if Δ_{2}U(n) = 2 begins a paeon, H if Δ_{2}U(n) = 0 is a hypercatalectic, and leave it undefined otherwise.

So φ(7) = φ(12) = φ(16) = φ(20) = P, φ(11) = φ(24) = H and φ(n) is not defined for other 7 ≤ n ≤ 24.

Proposition 3.3. {Δ_{2}U(n)}_{n=7}^{∞} consists only of feet.

Proof. By Definition 3.2, this is equivalent to saying that there are no p-blocks

n  T(n)  Δ_{2}T(n)  R(n)  Δ_{2}R(n) Δ_{2}U(n) φ(n)
n_{0} − 3  t_{1} − 2  2  ?  0  0  −
n_{0} − 2  t_{0} − 2  ?  r_{0} − 2  0  0  −
n_{0} − 1  t_{1} − 2  0  r_{1}  ?  0  ?
n_{0}  t_{0}  2  r_{0}  2  2  P
n_{0} + 1  t_{1}  2  r_{1}  0  0  −
n_{0} + 2  t_{0} + 2  2  r_{0}  0  0  −
n_{0} + 3  t_{1}  0  r_{1}  0  0  −
n_{0} + 4 t_{0} + d_{4} + 2  d_{4}  r_{0} + 2  2  d_{4}  P or H
n_{0} + 5  t_{1} + 2  2  r_{1} + 2 − d_{4} 2 − d_{4}  2 − d_{4}  − or P
n_{0} + 6 t_{0} + d_{4} + 4  2  r_{0} + 2  0  0  −
n_{0} + 7 t_{1} − d_{4} + 4 2 − d_{4} r_{1} + 2 − d_{4}  0  0  −

Table 3.2: Function Values Over a Paeon

of length p > 5 in Δ_{2}U(n), or that if Δ_{2}U(n) = 2 and Δ_{2}U(n + 4) = 0 then Δ_{2}U(n + 5) = 2.

We proceed to prove the latter by induction. The enumeration in Note 3.1 shows the proposition holds for n = 7. In particular, Δ_{2}U(7) = Δ_{2}U(12) = 2 and Δ_{2}U(11) = 0. Assume that the proposition is true for all n less than some N > 7, that Δ_{2}U(N) = 2 and that Δ_{2}U(N + 4) = 0. Corollary 2.5 and induction tell us that for some nonnegative q, Δ_{2}U(N) = Δ_{2}U(N − 4) = … = Δ_{2}U(N − 4q) = Δ_{2}U(N −4q−5) = 2 and Δ_{2}U(i) = 0 for all other i in the interval [N −4q−5, N +4].

We can compute differences of T by expanding into these known values of Δ_{2}U: T (N +4)−T (N +2) = Δ_{2}T (N +4) = ∑_{i=N+2}^{N+4} Δ_{2}U(i) = 0, T (N −4q −2)−T (N − 4q−4) = Δ_{2}T (N−4q−2) = ∑_{i=N−4q−4}^{N−4q−2} Δ_{2}U(i) = 0, and T (N+2)−T (N−4q−2) = ∑_{i=1}^{2q+2} Δ_{2}T (N − 2i + 4) = ∑_{i=1}^{2q+2} ∑_{j=0}^{2} Δ_{2}U(N − 2i − j + 4) = 4q + 4.

So T (N + 4) = T (N − 4q − 4) + 4q + 4, R(N + 5) = N + 5 − T (N + 4) = 2 + N + 3 − T (N + 2) = R(N + 3) + 2, R(N + 5) = N − 4q + 1 − T (N − 4q − 4) < N and R(N + 5) = 2 + N − 4q − 1 − T (N − 4q − 2) = R(N − 4q − 1) + 2.

Let y := R(N + 5). Then Δ_{2}T (y − 2) = Δ_{2}U(N − 4q − 1) = 0. By Corollary 2.3, Δ_{2}U(y−2) = Δ_{2}U(y−3) = Δ_{2}U(y−4) = 0. By induction, Δ_{2}U(y−1) and Δ_{2}U(y) cannot both be zero, or else Δ_{2}U would have five consecutive zeroes somewhere before N, at y−4, y−3, y−2, y−1 and y. Therefore, Δ_{2}U(y)+Δ_{2}U(y−1)+Δ_{2}U(y− 2) = 2 = Δ_{2}T (y) = U(N+5)−T (R(N+5)−2) = U(N+5)−U(N+3) = Δ_{2}U(N+5) as required. □

Note that as with Proposition 2.2, other choices of initial values for T (such as {T (n)}_{n=1}^{3} := { 1, 2, 1 }) will render false the initial conditions for the induction in the proof of Proposition 3.3. In such cases, the spacing between nonzero members of {Δ_{2}U(n)} can grow without bound.

We now use our results so far to create Table 3.2, a tabulation of six of our functions over the course of a paeon beginning at n_{0}, followed possibly by a hypercatalectic. We express the values of the functions in terms of the boxed parameters t_{0}, t_{1}, r_{0}, r_{1} and d_{4}. (The paeon is followed by a hypercatalectic iff d_{4} = 0, that is, φ(n_{0} + 4) = H iff d_{4} = 0.)

This description of the intricate local relationship among the T, R and U sequences tells us how to easily compute the parameter values in one foot of Δ_{2}U from the parameter values in the preceding foot. Further, it will be fundamental to an understanding of how the occurrence of feet in Δ_{2}U relates to much earlier values of Δ_{2}T. This then constitutes the first of our three structural theorems.

Theorem 3.4 (Foot Pattern Theorem). Suppose the parameters n_{0}, t_{0}, t_{1}, r_{0}, r_{1} and d_{4} satisfy all of the following conditions: n_{0} ≥ 7, T (n_{0}) = t_{0}, T (n_{0}+1) = t_{1}, R(n_{0}) = r_{0}, R(n_{0} + 1) = r_{1}, Δ_{2}U(n_{0}) = 2 and Δ_{2}U(n_{0} + 4) = d_{4}. Then T (n), Δ_{2}T (n), R(n), Δ_{2}R(n), Δ_{2}U(n) and φ(n) have the values shown in Table 3.2.

Proof. Use Proposition 3.3 and Corollary 2.5 to calculate Δ_{2}U(n). Apply the Δ_{2} operator to Equation (2.2) to calculate Δ_{2}T (n) (and Proposition 3.3 for Δ_{2}T (n_{0} − 3)). Use Δ_{2}R(n) = 2 − Δ_{2}T (n − 1) to calculate Δ_{2}R(n). Use the definition of Δ_{2} to calculate R(n) and T (n). □

Since Δ_{2}U(n) := T (R(n)) − T (R(n − 2)), the preceding theorem shows that the reason Δ_{2}U(n_{0} + 1) = Δ_{2}U(n_{0} + 2) = Δ_{2}U(n_{0} + 3) = 0 is not because the values of T (n) at two distinct arguments of T happen to be equal, but rather because T is being evaluated at two equal values of R(n), respectively r_{1}, r_{0} and r_{1}. For this reason, these three zero terms immediately following any 2 in {Δ_{2}U(n)} are rather uninteresting. Note that these three zeroes in each paeon of Δ_{2}U(n) correspond precisely to those terms for which Δ_{2}R(n) = 0, or equivalently the ones for which φ(n) is undefined.

Conversely when Δ_{2}R(n) = 2, that is, when φ(n) is defined:

Δ_{2}U(n_{0}) = T (r_{0}) − T (r_{0} − 2) = Δ_{2}T (r_{0})
Δ_{2}U(n_{0} + 4) = T (r_{0} + 2) − T (r_{0}) = Δ_{2}T (r_{0} + 2)

and so in both cases we obtain the key correspondence,

(3.2) Δ_{2}U(n) = (Δ_{2}T)(R(n)) = T (R(n)) − T (R(n) − 2)

We could also give an alternate definition: φ(n) = P if Δ_{2}U(n) + Δ_{2}R(n) = 4, and φ(n) = H if Δ_{2}U(n) + Δ_{2}R(n) = 2. Or also equivalently, φ(n) = P if Δ_{2}T (n) = 2 and Δ_{2}T (n−1) = 0, and φ(n) = H if Δ_{2}T (n) = 0 and Δ_{2}T (n−1) = 0.

Note 3.5. Δ_{2}T (n), Δ_{2}U(n) and Δ_{2}R(n) exhibit a recursive symmetry, just as do many other meta-Fibonacci sequences in the literature (e.g. in [12, 10]). As a result, there is a natural partition of their domain into generations (finite, consecutive strings of increasing length) such that certain function values within one generation can be expressed elegantly in terms of function values in preceding generations. We show in Theorem 3.14 that Equation (3.2) will express Δ_{2}U in one generation in terms of Δ_{2}T in the preceding generation.

Definition 3.6 (Generation). For any g > 0, let m_{g} := \frac{1}{2}(3^{g+1} + 5) = 3 + ∑_{i=0}^{g} 3^{i} and call the interval [m_{g}, m_{g+1} − 1] the gth generation, written gen(g). We partition the gth generation into two nonconsecutive subsequences: the gth even semigeneration sg_{0}(g) := { n ∈ gen(g) | n ≡ m_{g} (mod 2) } and the gth odd semigeneration sg_{1}(g) := { n ∈ gen(g) | n ≢ m_{g} (mod 2) }. For any sequence s(n), we will refer to the subsequence { s(n) | n ∈ gen(g), s(n) defined } as the gth generation of s and similarly for semigenerations. An even (odd) foot is one that starts in an even (odd) semigeneration.

Note that because the length 3^{g+1} of gen(g) is odd, m_{g} and m_{g+1} always have opposite parity. The foot that follows a paeon is always of the same parity, because the paeon has even length; while the foot that follows a hypercatalectic is always of opposite parity, because the hypercatalectic has odd length.

We list for future reference the first five values of m_{g}: 7, 16, 43, 124, 367.

Now we refine further our description of the structure of Δ_{2}U(n) within a generation. Once again we borrow from the terminology of Greek poetry, here to name sequences of feet with no internal hypercatalectics.

Definition 3.7 (Line). A line is a maximal subsequence of consecutive paeons and hypercatalectics in a generation, none of whose paeons is preceded by one of its hypercatalectics. We write a line as an overlined sequence of P s and H: (e.g.) \overline{P P P … P H}. An even (odd) line is one that starts in an even (odd) semigeneration, that is, one whose feet are all even (odd).

Proposition 3.3 tells us that a line is either a nonempty sequence of paeons followed by a hypercatalectic or a sequence of paeons at the end of a generation.

Example 3.8. The first generation of Δ_{2}U begins at Δ_{2}U(7), ends at Δ_{2}U(15) and consists of the nine numbers {Δ_{2}U(n)}_{n∈gen(1)} = { 2,0,0,0, 0, 2,0,0,0 }, the three feet {φ(n)}_{n∈gen(1)∩Dom φ} = { P, H, P } that form the first generation of φ, or the two lines \{ \overline{P H}, \overline{P} \}. The second generation of Δ_{2}U continues on from Δ_{2}U(16) and consists of the 27 numbers {Δ_{2}U(n)}_{n∈gen(2)} = { 2,0,0,0, 2,0,0,0, 0, 2,0,0,0, 0, 2,0,0,0, 0, 2,0,0,0, 2,0,0,0 \} or the four lines \{\overline{P P H}, \overline{P H}, \overline{P H}, \overline{P P} \}. The third generation of Δ_{2}U consists of the ten lines \{ \overline{P P P P H}, \overline{P H}, \overline{P H}, \overline{P H}, \overline{P P H}, \overline{P P H}, \overline{P H}, \overline{P H}, \overline{P H}, \overline{P P P P} \} .

As was the case with feet, there is an intricate relationship among the values of the T, R and U sequences on the paeons and hypercatalectic that make up a line. This is captured in the second of our three structural theorems:

Theorem 3.9 (Line Pattern Theorem). Suppose T (n_{0}) = t_{0}, T (n_{0} + 1) = t_{1}, R(n_{0}) = r_{0}, R(n_{0} +1) = r_{1}, and Δ_{2}U(n_{0}) is the beginning of a line of q paeons and a hypercatalectic, ending therefore at Δ_{2}U(n_{0} + 4q). Then T (n), Δ_{2}T (n), R(n), Δ_{2}R(n), Δ_{2}U(n) and φ(n) have the following values shown in Table 3.3.

Proof. By Definition 3.7, Δ_{2}U(n_{0}) = Δ_{2}U(n_{0} + 4) = … = Δ_{2}U(n_{0} + 4q − 4) = Δ_{2}U(n_{0} + 4q + 1) = 2 and all other intervening values of Δ_{2}U are zero. The first two rows of the table depend on whether or not the line begins a generation (and hence whether or not the preceding foot is a paeon or a hypercatalectic), and its values can be computed using Foot Pattern Theorem 3.4. The rest of the result follows from q applications of Foot Pattern Theorem 3.4, setting n_{0} successively to the start of each of these paeons. □

We observe that the feet within a line all have the same parity, and the lines within a generation alternate in parity. Further, the lines within a generation are essentially symmetric about the middle of the generation; for example, in the third

n − n_{0}  T(n)  Δ_{2}T(n)  R(n)  Δ_{2}R(n) Δ_{2}U(n) φ(n)
−2  t_{0} − 2  ?  r_{0} − 2  0  0  −
−1  t_{1} − 2  0  r_{1}  ?  0  ?
.....................................................................................................................
0  t_{0}  2  r_{0}  2  2  P
1  t_{1}  2  r_{1}  0  0  −
⋮  ⋮  ⋮  ⋮  ⋮  ⋮  −
4q − 4 t_{0} + 4q − 4  2  r_{0} + 2q − 2  2  2  P
4q − 3 t_{1} + 2q − 2  2  r_{1}  0  0  −
4q − 2 t_{0} + 4q − 2  2  r_{0} + 2q − 2  0  0  −
4q − 1 t_{1} + 2q − 2  0  r_{1}  0  0  −
4q  t_{0} + 4q − 2  0  r_{0} + 2q  2  0  H
.....................................................................................................................
4q + 1  t_{1} + 2q  2  r_{1} + 2  2  2  P
4q + 2  t_{0} + 4q  2  r_{0} + 2q  0  0  −

Table 3.3: Function Values Over a Line

generation, the fifth and sixth are identical, as are the fourth, and seventh, third and eighth, and second and ninth. The first and tenth lines have identical paeons, but the first line ends in a hypercatalectic while the tenth does not. In fact, it is precisely this symmetry that led us to the specification of m_{g} as the start of the gth generation.

We will show in Theorem 3.15, to which we are now building, that a generation consists entirely of lines, with no excess terms. Further, the proof of that theorem will demonstrate how the values of Δ_{2}U(n) in the gth generation are determined by the values of Δ_{2}T (n) in the (g − 1)st generation. This provides an understanding of how successive generations interrelate. In order to get there, we require some additional background.

We mentioned in Note 3.5 that the gth generation of Δ_{2}U would be expressed in terms of the (g − 1)st generation of Δ_{2}T. It turns out that the natural restriction of the function R to those n in the gth generation that start a foot is one to one onto the (g − 1)st generation; for each such n, the value of R(n) is the unique r in the (g − 1)st generation for which Δ_{2}T (r) = Δ_{2}U(n). We can then use the inverse of this map to construct a beautiful correspondence from the (g − 1)st generation to the gth, as we will soon show.

Example 3.10. We illustrate this inverse map of R with a simple example. Generation 2 begins at n = 16 and ends at n = 42. We know from Note 3.1 and Theorems 3.4 and 3.9 that the feet of Δ_{2}U in generation 2 begin at n = 16, 20, 24, 25, 29, 30, 34, 35 and 39. From Table 3.1 we have R(16) = 7, R(20) = 9, R(24) = 11, R(25) = 8, R(29) = 10, R(30) = 13, R(34) = 15, R(35) = 12, and R(39) = 14. Observe that all of these values of R(n) are distinct, and that they include all of the integers from 7 to 15, which is precisely the first generation. So the inverse of R, evaluated on the first generation gives the beginnings of all of the feet in the second generation of Δ_{2}U. In this way, the successive generations of T are interrelated.

We now show that the invertibility property holds.

Proposition 3.11. Let E be the set of even numbers and D = Dom φ. Then R|_{D∩E} begins with 5 and increases (strictly) only by two, while R|_{D\E} begins with 4 and also increases only by two.

Proof. By Equation (3.1) and Note 3.1, R(7) = 4, R(12) = 5. The result follows from the values of R(n_{0} + 4) and R(n_{0} + 5) given in Foot Pattern Theorem 3.4. □

We don’t know yet that Ran(R|_{Dom φ}) is all of [4, ∞). This will be established after we show in Theorem 3.15 that each generation of Δ_{2}U(n) has at least one hypercatalectic, so Ran(R|_{Dom φ}) flips parity infinitely often. We now name the inverse of this restriction of R.

Definition 3.12. For n ∈ Dom φ, let f(R(n)) = n. That is, if Δ_{2}R(n) = 2, then f(R(n)) = n.

In Example 3.10, we had f(7) = 16, f(8) = 25, f(9) = 20 and so on. Also, since f is bijective by construction, R(f(r)) = r when f(r) is defined. Observe that R(f(7)) = R(16) = 7 and f(7) = 16 and R(7) = 4 so f(7) ≡ R(7) ≢ 7 (mod 2).

Corollary 3.13. When f(r) is defined, f(r) ≡ R(r) ≢ r (mod 2). If r ∈ Ran R then f(n) is defined for all n ≡ r (mod 2) in [4, r]. f(r) is the smallest member of the set R^{−1}(r).

Proof. By Proposition 3.11, R(n) is even when n is odd, and vice versa. Since f is the inverse of a restriction of R, f(r) is odd when r is even, and vice versa.

Also by Proposition 3.11, the range of R|_{D∩E} is a consecutive sequence of odd numbers starting at 5 with no gaps, so if an odd r ∈ Ran R, then Ran R also includes all lesser odd numbers down to 5; and similarly for even r.

By Theorem 3.4, Δ_{2}R(n) is 2 at the beginning of a foot in Δ_{2}U and 0 elsewhere. Therefore, among all the n for which R(n) is equal to a particular r, it is the smallest one which belongs to Dom φ. □

We are now close to demonstrating that our partition of the domains of our functions into generations is a natural one, by showing that the values of functions on one generation depend solely on the values of functions in the immediately preceding generation. As we illustrated in Example 3.10, if n belongs to the gth generation, then R(n) belongs to the (g − 1)st generation. Therefore, if r belongs to the gth generation, then f(r) belongs to the (g + 1)st generation.

It turns out though that f does much more than simply map one generation into the next. If for some r in the gth generation Δ_{2}T (r) = 2, then f(r) is the beginning of a paeon in the (g + 1)st generation of Δ_{2}U: that is, φ(f(r)) = P. Conversely if Δ_{2}T (r) = 0, then f(r) is the beginning of a hypercatalectic of Δ_{2}U and φ(f(r)) = H. Thus f establishes a correspondence between each member of one generation and each foot of Δ_{2}U in the next generation, incidentally accounting for how the successive generations grow.

Figure 3.4 displays this correspondence for the first two generations, and elaborates on the consequences of the parity principle of Corollary 3.13. As shown in Example 3.8, the first generation of Δ_{2}U consists of the feet {P, H, P }. According to Foot Pattern Theorem 3.4, it follows that the first generation of Δ_{2}T must be

Figure 3.4: How Successive Generations Correspond

{2, 2, 2, 0; 0; 2, 2, 2, 0}, where semicolons indicate the ends of the feet in Δ_{2}U. In Figure 3.4 we show the four entries of Δ_{2}T that correspond to each paeon of Δ_{2}U enclosed in a parallelogram, and the single (zero) entry of Δ_{2}T that corresponds to a hypercatalectic of Δ_{2}U enclosed in a triangle.

The action of f on members of the first generation determines the structure of the second generation. If we have r such that Δ_{2}T (r) = 2, then f(r) marks the beginning of a paeon in Δ_{2}U: that is, φ(f(r)) = P, as indicated by the dashed lines in the figure. Likewise dashed lines connect the points at which Δ_{2}T (r) = 0 to the points where φ(f(r)) = H.

Successive integers in the first generation alternate in parity. By Corollary 3.13, their images under f must also alternate in parity. However, since all of the feet in a line must have the same parity, the image under f of the integers corresponding to a paeon in Δ_{2}U lie in two separate lines of opposite parity. The lines in the second generation are enclosed in boxes, and arrows indicate the intertwined order in which they are to be concatenated to form the second generation.

Observe that we can now easily count the number of feet and lines in each successive generation. Since each foot in the first generation of Δ_{2}U ends at a

n  T(n) Δ_{2}T(n)  R(n)  Δ_{2}R(n) Δ_{2}U(n) φ(n)
m_{g} − 4 3^{g} − 2  2  m_{g−1} − 2  2  2  P
m_{g} − 3  3^{g}  2  m_{g−1} − 1  0  0  −
m_{g} − 2  3^{g}  2  m_{g−1} − 2  0  0  −
m_{g} − 1  3^{g}  0  m_{g−1} − 1  0  0  −
..................................................................................................................................
m_{g}  3^{g} + 2  2  m_{g−1}  2  2  P
m_{g} + 1 3^{g} + 2  2  m_{g−1} − 1  0  0  −
m_{g} + 2 3^{g} + 4  2  m_{g−1}  0  0  −

Table 3.5: Function Values Near the End of a Generation

point where Δ_{2}T is zero, it corresponds to a line-ending hypercatalectic in the second generation of Δ_{2}U. So, the number of hypercatalectics in one generation is the same as the number of feet in the preceding generation. And hence, the number of lines in one generation is one more (taking into account the last line that lacks a hypercatalectic) than the number of feet in the preceding generation.

The following theorem proves the correspondence between 0s and 2s and H’s and P ’s, and will be the foundation for much of the rest of the paper.

Theorem 3.14 (Generational Correspondence Theorem). The diagram

Dom f \overrightarrow{⟵}_{R}^{f} Ran f
Δ_{2}T ↓  ^{φ}↓
{0, 2} ⟶_{2↦P}^{0↦H} {H, P }

commutes. That is, for 4 ≤ r ∈ Dom f, φ(f(r)) = P iff Δ_{2}T (r) = 2.

Proof. If φ(f(r)) = P, then by Equation (3.2), 2 = Δ_{2}U(f(r)) = Δ_{2}T (R(f(r))) = Δ_{2}T (r). If φ(f(r)) = H, then 0 = Δ_{2}U(f(r)) = Δ_{2}T (R(f(r))) = Δ_{2}T (r). □

We are now ready to present the last of our three structural theorems, which will rely on Theorem 3.14 to express each generation in terms of its predecessor. This will prove that the correspondence illustrated in Figure 3.4 does map each generation exactly onto the next.

Theorem 3.15 (Generation Pattern Theorem). The gth generation of Δ_{2}U consists entirely of 3^{g−1} +1 lines. Its last line consists only of (odd) paeons, the last of which has Foot Pattern Theorem 3.4 parameters n_{0} = m_{g+1} − 4, t_{0} := T (n_{0}) = 3^{g+1}−2, t_{1} := T (n_{0}+1) = 3^{g+1}, r_{0} := R(n_{0}) = m_{g}−2 and r_{1} := R(n_{0}+1) = m_{g}−1.

Proof. The values of T and Δ_{2}U necessary to verify the result for g = 1 and g = 2 have been listed above in Note 3.1. We proceed to larger g by induction, assuming that the results hold for all generations before the gth. In particular, applying Foot Pattern Theorem 3.4 to the last foot of the (g − 1)st generation gives us the first four rows of the key function values shown in Table 3.5.

To obtain the last three of the rows, we need to show that the gth generation begins with a paeon and not a hypercatalectic. Observe that by induction the (g − 1)st generation begins with a paeon, so the Foot Pattern Theorem 3.4 applied to n_{0} = m_{g−1} − 4 gives us T (m_{g−1}) = 3^{g−1} + 2 and Δ_{2}T (m_{g−1}) = 2. Since Δ_{2}U(m_{g}) begins a foot, Equation (3.2) tells us that Δ_{2}U(m_{g}) = Δ_{2}T (m_{g−1}) = 2 and the start of the first foot in the gth generation of Δ_{2}U corresponds with the first term in the (g − 1)st generation of Δ_{2}T, as desired. Apply Theorem 3.4 to n_{0} = m_{g} to fill in the rest of the values.

Next, we show that f maps gen(g − 1) onto gen(g) ∩ Dom φ, as shown for g = 2 in Figure 3.4. By Corollary 3.13 and the fact that all generations have odd length, we will know then that f maps sg_{i}(g − 1) onto sg_{i}(g) ∩ Dom φ for i = 0, 1.

We begin at R(m_{g}) = m_{g−1}, so f(m_{g−1}) = m_{g}, for which Theorem 3.14 with r = m_{g−1} gives us a correspondence between Δ_{2}T (m_{g−1}) = 2 and φ(f(m_{g−1})) = P. We claim that if we continue on through all of the (g − 1)st generation of Δ_{2}T, the values of f will not overrun the end of the gth generation. To check this, we have to carefully count twos, zeros, paeons and hypercatalectics.

We look first at the twos and zeroes in the (g − 1)st generation of Δ_{2}T. In the even case, ∑_{n∈sg_{0}(g−1)} Δ_{2}T (n) = T (m_{g} − 1) − T (m_{g−1} − 2) = 3^{g} − 3^{g−1} = 2 · 3^{g−1} and (m_{g} − 1) − (m_{g−1} − 2) = 3^{g} + 1, so Δ_{2}T (n) has the value two 3^{g−1} times and zero the remaining \frac{1}{2}(3^{g} + 1) − 3^{g−1} = \frac{1}{2}(3^{g−1} + 1) times. In the odd case, ∑_{n∈sg_{1}(g−1)} Δ_{2}T (n) = T (m_{g} − 2) − T (m_{g−1} − 1) = 3^{g} − 3^{g−1} = 2 · 3^{g−1} and (m_{g} −2)−(m_{g−1} −1) = 3^{g} −1, so Δ_{2}T (n) is two 3^{g−1} times and zero the remaining \frac{1}{2}(3^{g} − 1) − 3^{g−1} = \frac{1}{2}(3^{g−1} − 1) times.

Using the correspondence of Theorem 3.14, we conclude that in the gth generation the \frac{1}{2}(3^{g−1} + 1) even hypercatalectics outnumber the \frac{1}{2}(3^{g−1} − 1) odd hypercatalectics by one. Thus, the correspondence ends (after a total of 3^{g−1} + 1 lines) with an even hypercatalectic followed by a run of odd paeons. There are 3^{g−1} even paeons and 3^{g−1} odd paeons. Adding together the lengths of all the paeons and hypercatalectics gives 4 · 3^{g−1} + 4 · 3^{g−1} + \frac{1}{2}(3^{g−1} + 1) + \frac{1}{2}(3^{g−1} − 1) = 3^{g+1}, which is exactly the length of the gth generation.

Finally, we need to calculate the Foot Pattern Theorem 3.4 parameters when n_{0} = m_{g+1} − 4 at the end of the gth generation. Let P_{0} = P_{1} = 3^{g−1}, H_{0} = \frac{1}{2}(3^{g−1} + 1) and H_{1} = \frac{1}{2}(3^{g−1} − 1) be respectively the number of even paeons, odd paeons, even hypercatalectics and odd hypercatalectics in the gth generation. Then by repeated application of Line Pattern Theorem 3.9, r_{0} = (m_{g−1} − 1) + 2H_{0} + 2(P_{1} − 1) = m_{g−1} − 1 + 3^{g−1} + 1 + 2 · 3^{g−1} − 2 = m_{g−1} + 3^{g} − 2 = m_{g} − 2, r_{1} = m_{g−1} + 2H_{1} + 2P_{1} = m_{g} − 1, t_{0} = (3^{g} + 2) + 4P_{0} + 2P_{1} − 4 = 3^{g+1} − 2 and t_{1} = (3^{g} + 2) + 4P_{0} + 2P_{1} − 2 = 3^{g+1}. □

4. Some Interesting Properties of the Three-Term Case

We continue to use T, U and R as defined in Equation (3.1). In this section we explore a variety of interesting properties of the T sequence, as well as of the Δ_{2}T and Δ_{2}U difference sequences.

Before we proceed, we need to present a short technical lemma concerning the relationship between differences in the T sequence and differences in the U sequence.

Lemma 4.1. Δ_{d}T (n) = ∑_{i=0}^{k−1} Δ_{d}U(n − i) = ∑_{i=0}^{d−1} Δ_{k}U(n − i).

Proof. Rearrange the summation and difference operators as follows:

Δ_{d}T (n) = ∑_{i=0}^{k−1} Δ_{d}U(n − i) = ∑_{i=0}^{k−1} U(n − i) − ∑_{i=0}^{k−1} U(n − d − i)

= ∑_{i=0}^{k+d−1} U(n − i) − ∑_{i=0}^{d−1} U(n − k − i) − ∑_{i=0}^{k−1} U(n − d − i)

= ∑_{i=0}^{d−1} U(n − i) − ∑_{i=0}^{d−1} U(n − k − i) = ∑_{i=0}^{d−1} Δ_{k}U(n − i) □

Allenby and Smith [1] first observed that there is no n for which T (n) = T (n − 2) = T (n − 4), or equivalently, for which Δ_{2}T (n) = Δ_{2}T (n − 2) = 0. This follows directly from Foot Pattern Theorem 3.4.

Proposition 4.2. There do not exist n for which Δ_{2}T (n) = Δ_{2}T (n − 2) = 0.

Proof. Follows directly from Foot Pattern Theorem 3.4. □

In fact, Proposition 4.2 is equivalent to Proposition 3.3: if Δ_{2}T (n) = Δ_{2}T (n − 2) = 0, then by Corollary 2.3, Δ_{2}U(n) = Δ_{2}U(n−1) = … = Δ_{2}U(n−4) = 0; while if Proposition 4.2 holds then for any n, 0 ≠ Δ_{4}T (n) = Δ_{2}T (n) + Δ_{2}T (n − 2) = Δ_{2}U(n) + Δ_{2}U(n − 1) + 2Δ_{2}U(n − 2) + Δ_{2}U(n − 3) + Δ_{2}U(n − 4), so Δ_{2}U never has five consecutive zeroes.

One of the more interesting properties of Conolly’s sequence (1.2), our case k = 2, is that it consists of a monotonically increasing sequence of integers whose frequency counts form the Gray binary sequence (Sloane Sequence A001511 [13]), omitting its first term. We can prove the analogous property concerning the frequency counts of T (n) for k = 3 and in so doing answer a conjecture given in Allenby and Smith [1].

Theorem 4.3. T (n) = T (n + 1) = T (n + 2) if and only if n = m_{g} − 3 for some g.

Proof. (First conjectured in Allenby and Smith [1].) The Foot Pattern Theorem 3.4 parameters proven in Generation Pattern Theorem 3.15 give us the required equality when n = m_{g} − 3. We need to show then that equality does not occur elsewhere.

Suppose n^{∗} is a minimal counterexample. That is, n^{∗} + 3 is not the start of a generation, t := T (n^{∗}) = T (n^{∗} + 1) = T (n^{∗} + 2) and no smaller counterexamples exist. By Theorem 3.4, φ(n^{∗} − 1) = P, R(n^{∗} + 1) = R(n^{∗} − 1) = n^{∗} − t + 1 and R(n^{∗} + 2) = R(n^{∗}) = R(n^{∗} − 2) = n^{∗} − t + 2. By Lemma 4.1, 0 = Δ_{1}T (n^{∗} + 2) = Δ_{3}U(n^{∗} + 2) = T (n^{∗} − t + 2) − T (n^{∗} − t + 1) = Δ_{1}T (n^{∗} − t + 2).

By Theorem 3.4, Lemma 4.1 and Equation (3.1), we have 2 = Δ_{2}U(n^{∗} − 1) = (Δ_{2}T)(R(n^{∗} − 1)) = (Δ_{2}T)(R(n^{∗} + 1)) = (Δ_{2}U)(R(n^{∗} + 1)) + (Δ_{2}U)(R(n^{∗} + 1) − 1) + (Δ_{2}U)(R(n^{∗} + 1) − 2) = Δ_{2}U(n^{∗} − t + 1) + Δ_{2}U(n^{∗} − t) + Δ_{2}U(n^{∗} − t − 1). Exactly one of these three terms is equal to two: but which?

If Δ_{2}U(n^{∗} − t − 1) = 2, then by Theorem 3.4, T (n − t) = T (n − t + 2); and since we have already observed that T (n − t + 1) = T (n − t + 2) we can invoke the minimality of n^{∗} to conclude that there must be a g such that m_{g} = n^{∗} −t+3. But then R(n^{∗} − 1) = m_{g} − 2 and n^{∗} − 1 = f(m_{g} − 2) = m_{g+1} − 4 so n^{∗} = m_{g+1} − 3, in contradiction to our hypothesis.

If Δ_{2}U(n^{∗} − t + 1) = 2, then there must be a g such that m_{g} = n^{∗} − t + 1 and similarly n^{∗} = m_{g+1} + 1, which contradicts the observation in Generation Pattern Theorem 3.15 that the second and third members of any generation of T differ.

Finally, if Δ_{2}U(n^{∗} − t) = 2, then there must be a g such that m_{g} = n^{∗} − t + 4. R(m_{g+1} − 6) = m_{g} − 4 and R(m_{g+1}) = m_{g}, so by monotonicity R attains the value m_{g} − 2 at most twice, which contradicts R(n^{∗} − 2) = R(n^{∗}) = R(n^{∗} + 2) = m_{g} − 2.

So none of the three choices is possible, and the original assumption of a counterexample must have been false. □

Corollary 4.4. There is no n for which T (n) = T (n + 1) = T (n + 2) = T (n + 3).

Proof. This is proven directly in Allenby and Smith [1], but follows simply from Proposition 4.3. □

In fact, it turns out that even two consecutive terms of T are rarely equal. Looking back at Figure 1.6, we can see that the points at which the two lines intersect all occur near the ends of generations.

Corollary 4.5. T (n) = T (n + 1) if and only if there is a g such that n ∈ { m_{g} − 5, m_{g} − 3, m_{g} − 2, m_{g} }.

Proof. If n ∈ { m_{g} − 5, m_{g} − 3, m_{g} − 2, m_{g} }, then by Generation Pattern Theorem 3.15, T (n) = T (n+1). Conversely, suppose T (n) = T (n+1) and consider where the nearest paeon starts. If φ(n) = P, then by Foot Pattern Theorem 3.4, T (n − 3) = T (n − 2) = T (n − 1) = T (n) − 2 and by Theorem 4.3, n = m_{g} for some g. If φ(n + 1) = P, then similarly n = m_{g} − 5. If φ(n + 2) = P, then n = m_{g} − 2. Otherwise, T (n) = T (n + 1) = T (n + 2) and n = m_{g} − 3. □

Corollary 4.6. There are infinitely many n for which T (n) = T (n + 1) and T (n + 2) = T (n + 3).

Proof. This was conjectured in Allenby and Smith [1], and follows from Corollary 4.5. The values of n for which this holds are precisely those that can be written as n = m_{g} − 2 for some g. It is shown in [1] that such n must satisfy { Δ_{1}T (n − 1), Δ_{1}T (n + 5) } = { −2, 2 } (in some order), which follows from the Generation Pattern Theorem 3.15. This theorem also tells us that if T (n) = T (n + 1) then either T (n − 2) = T (n − 1) or T (n + 2) = T (n + 3). □

Corollary 4.7. There is no n for which T (n) = T (n + 1), T (n + 2) = T (n + 3) and T (n + 4) = T (n + 5).

Proof. This is proven directly in Allenby and Smith [1], but follows simply from Corollary 4.5. □

Theorem 4.3 and the four corollaries that follow from it provide the characterization of the frequency counts that we seek. Because the case k = 3 gives a nonmonotonic sequence (unlike Conolly’s k = 2), its repeated values can be either consecutive or nonconsecutive. We define the consecutive repeated values of a sequence

\{\overbrace{a_{1},…, a_{1}}^{n_{1}}, \overbrace{a_{2},…, a_{2}}^{n_{2}}, …, \overbrace{a_{m},…, a_{m}}^{n_{m}}\}

where a_{1} ≠ a_{2}, a_{2} ≠ a_{3}, …, a_{m−1} ≠ a_{m} in the obvious way as the sequence {n_{1},…, n_{m}}. Then we can summarize these results in the following theorem.

Proposition 4.8. The consecutive repeated values of the gth generation of T are

\{2, \overbrace{1,…, 1}^{3^{g+1}−7}, 2, 3\}

Proof. This is a restatement of Corollary 4.5.

In section 3 we showed the crucial role played by the Δ_{2}U sequence that leads to our understanding the detailed structure of the T sequence. It turns out that the Δ_{2}U sequence has many fascinating properties, including beautiful symmetries both within and between generations, that make it of independent interest.

We begin by giving a more detailed description of the structure of each generation of Δ_{2}U. By Generation Pattern Theorem 3.15, the gth generation of Δ_{2}U consists entirely of 3^{g−1} + 1 lines.

Definition 4.9. For g > 0 and i ∈ [0, 3^{g−1}] let q_{i,g} be the number of paeons in the ith line (numbered starting with the zeroth) of the gth generation of Δ_{2}U.

In Example 3.8 we showed that q_{0,1} = q_{1,1} = 1; q_{0,2} = 2, q_{1,2} = q_{2,2} = 1, q_{3,2} = 2; q_{0,3} = 4, q_{1,3} = q_{2,3} = q_{3,3} = 1, q_{4,3} = q_{5,3} = 2, q_{6,3} = q_{7,3} = q_{8,3} = 1 and q_{9,3} = 4.

Proposition 4.10. The sequence consisting of the number of paeons in each even line in the (g + 1)st generation of Δ_{2}U can be expressed in terms of the number of paeons in the lines in the gth generation of Δ_{2}U as follows:

\{ 2q_{0,g}, \overbrace{1, …, 1}^{q_{1,g}}, 2q_{2,g}, \overbrace{1, …, 1}^{q_{3,g}}, 2q_{4,g}, \overbrace{1, …, 1}^{q_{5,g}}, …, 2q_{3^{g−1}−1,g}, \overbrace{1, …, 1}^{q_{3^{g−1},g}} \}.

Proof. Generational Correspondence Theorem 3.14 (see Figure 3.4), together with Generation Pattern Theorem 3.15, shows that each even (odd) paeon in a generation produces two paeons in the next even (odd) semigeneration and a paeon and a hypercatalectic in the next odd (even) semigeneration, while an even (odd) hypercatalectic simply produces an even (odd) hypercatalectic. Thus each paeon contributes a single paeon line (i.e. P H) to the next subgeneration of opposite parity and two paeons (P P) to the next subgeneration of equal parity. The number of even paeons in each even line in the gth generation therefore appears doubled in the (g + 1)st even semigeneration, alternating with runs of single-paeon lines. □

Recall that a sequence is palindromic if it has reflective symmetry. Two basic transformations that preserve palindromicity are that of replacing every occurrence of a member of a sequence by a palindromic subsequence, and that of applying any transformation to the lengths of consecutive runs of identical members in a sequence. For example, the string ‘AABABAA’ is palindromic and changing every ‘AA’ to ‘A’ and every ‘B’ to ‘CDC’ gives ‘ACDCACDCA’, which remains palindromic. We use these palindromicity-preserving transformations and Foot Pattern Theorem 3.4 to show the following generational palindromicity property, which we can use to find q_{i,g} for odd i.

Theorem 4.11. Each generation of Δ_{2}U(n) consists of a palindromic sequence of feet.

Proof. The result is true for the first generation, which consists of { P, H, P }: see Example 3.8. We proceed by induction, assuming that it is true for all generations before the gth.

By induction, the (g − 1)st generation of Δ_{2}U is a palindromic sequence of feet. Transforming that sequence using { P ↦ 02220, H ↦ 0 } followed by { 000 ↦ 00, 00 ↦ 0 } gives us a palindromic sequence, which Foot Pattern Theorem 3.4 lets us recognize as the (g − 1)st generation of Δ_{2}T, preceded by a zero. Because the length of every generation is odd, it follows that the (g − 1)st even semigeneration of Δ_{2}T (n) is the reverse of the (g − 1)st odd semigeneration of Δ_{2}T (n), followed by a zero. Then by Generational Correspondence Theorem 3.14 (see Figure 3.4), the sequence { q_{0,g}, q_{2,g}, q_{4,g},… } is the reverse of { q_{1,g}, q_{3,g}, q_{5,g},… }. Thus, the entire sequence {q_{i,g}}_{i=0}^{3^{g}} is palindromic and all the feet in the gth generation form a palindromic sequence. □

Corollary 4.12. Each generation of Δ_{2}T (n) consists of a palindromic sequence of 2s and 0s, followed by an extra 0.

Proof. Follows from Theorem 4.11 by application of Foot Pattern Theorem 3.4. □

Proposition 4.13. q_{i,g} is always a power of 2.

Proof. The proposition is true for g = 1, since q_{0,1} = q_{1,1} = 1. Assume inductively that the proposition is true for all generations preceding the gth. Proposition 4.10 tells us that q_{i,g} for even i is a power of 2; and Theorem 4.11 tells us that the q_{i,g} for odd i have the same (power of 2) values in reverse order. □

We now use what we have learned about the structure of our sequences to obtain some quantitative properties of the sequences.

Proposition 4.14. For positive g and 0 ≤ x ≤ m_{g+1} − 4, the sum T (m_{g} + x) + T (m_{g+1} − 4 − x) = 3^{g} + 3^{g+1} is constant. For 0 ≤ y ≤ m_{g+1} − 6, the sum U(m_{g} + y) + U(m_{g+1} − 6 − y) = 3^{g−1} + 3^{g} is constant.

Proof. Follows readily from palindromicity of Δ_{2}T (n) and Δ_{2}U(n) within the gth generation. □

Proposition 4.15. The mean value of the gth generation of T (n) is 2·3^{g} +1. The mean value of the gth generation of U(n) is 2 · 3^{g−1} + \frac{5}{9}.

Proof. Follows from Proposition 4.14 and the values indicated by Generation Pattern Theorem 3.15 and Pattern Theorem 3.4 for the last few values in the gth generations of T (n) and U(n). □

Corollary 4.16. The asymptotic value of \frac{T (n)}{n} is \frac{2}{3}.

Proof. The mean value of n in the gth generation is (m_{g} + m_{g+1} − 1)/2 = (3^{g+1} + 5 + 3^{g+2} + 5 − 2)/4 = 3^{g+1} + 2 = 3 · 3^{g} + 2. By Proposition 4.15, the mean value of T in the same generation is 2 · 3^{g} + 1. The ratio (2 · 3^{g} + 1)/(3 · 3^{g} + 2) approaches \frac{2}{3} as g approaches infinity. □

Proposition 4.17. The mean value of the gth generation of Δ_{2}T (n) is \frac{4}{3}. The mean value of the gth generation of Δ_{2}U(n) is \frac{4}{9}.

Proof. In the proof of the Generation Pattern Theorem 3.15, we counted 2 · 3^{g−1} paeons in the gth generation, which has length 3^{g+1}. Recall from Foot Pattern Theorem 3.4 that at a hypercatalectic, Δ_{2}T (n) = Δ_{2}U(n) = 0; while each paeon contributes 6 to the sum of Δ_{2}T and 2 to the sum of Δ_{2}U. □

We conclude this section with an observation whose generalization will play a key role in the next section.

Proposition 4.18. Δ_{4}U(n) ∈ { 0, 2 }.

Proof. The result is easily verified for small n. Expand Δ_{6}U(n) in two ways to obtain Δ_{4}U(n) = Δ_{4}U(n−2)+(Δ_{2}U(n)−Δ_{2}U(n−4)). By Foot Pattern Theorem 3.4, Δ_{6}U has period 2 (alternating between the values 2 and 0) on any run of paeons, and is 0 at a hypercatalectic. □

To date, we have not yet succeeded in proving that no closed form exists for T (n). Nonetheless, the tools that we have created have facilitated the analysis which normally follows from the discovery of a closed form, namely: a complete characterization of the structure of the sequence, the computation of mean and asymptotic values, and the rapid calculation of large values of the sequence.

5. The Structure for General Odd k

In the preceding two sections, we examined the case k = 3 in great detail. In this section, we find that most of our results generalize to greater odd k. In the recursion (1.6) we again set a = 0 and assume the initial conditions T_{0,k}(n) = 1 for 1 ≤ n ≤ k with k odd. We will refer to this sequence as T (n), to R_{0,k}(n) as R(n) and to U_{0,k}(n) as U(n):

(5.1)  T (n) := U(n) + U(n − 1) + … + U(n − k + 1), n > k
U(n) := T (R(n)), n > 1
R(n) := n − T (n − 1), n > 1

When k = 3, the behaviour of the recursion can largely be characterized in terms of the pattern of feet in the values of Δ_{k−1}U, most of which have length k + 1 = 4, with the occasional hypercatalectic. For general odd k, we find that Δ_{k−1}U follows the same pattern, consisting mostly of paeons now of length k + 1, with a hypercatalectic of length 1 every now and then.

In order to prove that there is only one zero or hypercatalectic between runs of paeons in Δ_{k−1}U — which is not the case for even k — we will need to prove an additional property of these runs of paeons. This is that paeons always come in groups of \frac{k−1}{2}, a property which was trivial for k = 3, where \frac{k−1}{2} = 1.

It happens that Δ_{k+1}U has repeating patterns resembling feet of length k − 1, also with the occasional extra term resembling a hypercatalectic. We will show that the hypercatalectics in Δ_{k−1}U always coincide with the analogous disruptions in Δ_{k+1}U. This gives the recursion an additional level of structure: paeons always come grouped in polypaeons of length lcm(k − 1, k + 1) = \frac{1}{2}(k^{2} − 1). That is, a polypaeon consists of \frac{k−1}{2} consecutive paeons.

We begin by generalizing our previous definitions and defining what we mean by a polypaeon.

Definition 5.1. A paeon is a sequence \{ k −1, \overbrace{0,…, 0}^{k} \} of k +1 consecutive values of Δ_{k−1}U(n). A hypercatalectic is a singleton sequence { 0 }, immediately preceded in {Δ_{k−1}U(n)} by a paeon. A foot is either a paeon or a hypercatalectic. A polypaeon is a sequence of \frac{1}{2}(k − 1) consecutive paeons. For convenience, we will write { P } interchangeably with the paeon { k−1, 0,…, 0 } and likewise { H } with the hypercatalectic { 0 } when listing values of Δ_{k−1}U. We also define φ(n) on a subset of the natural numbers as the symbol P if Δ_{k−1}U(n) = k−1 begins a paeon, H if Δ_{k−1}U(n) = 0 is a hypercatalectic, and leave it undefined otherwise.

We now generalize Proposition 2.2 to facilitate proving the polypaeon structure.

Proposition 5.2. For fixed odd k > 1, all even d ∈ [0, k − 1] and any n > k, both |Δ_{d}U(n)| and Δ_{d}T (n) belong to the set { 0, k − 1 }.

Proof. The case k = 3 was already proven in Proposition 2.2, and the case d = 0 is trivial. We assume therefore in what follows that k > 3 and d > 0.

As in the proof of Proposition 2.2, we proceed by induction and leave it to the reader to verify that the result holds for n ≤ 2k. Assume then that n > 2k and that the result holds for lesser n and all relevant d.

Δ_{d}U(n) := T (R(n)) − T (R(n − d)) = (Δ_{x}T)(R(n)), where x = Δ_{d}R(n) = d − Δ_{d}T (n − 1). By the induction assumption, Δ_{d}T (n − 1) ∈ { 0, k − 1 }, so x ∈ {d, d − k + 1}. In either case, |x| is even and in [0, k − 1] and the greater of R(n) and R(n − d) is strictly less than n, so we can apply induction again to find that |(Δ_{x}T)(R(n))| ∈ { 0, k − 1 } and hence. |Δ_{d}U(n)| ∈ { 0, k − 1 }.

Observe that Δ_{d}T (n) + Δ_{k−1−d}T (n − d) = Δ_{k−1}T (n). By Proposition 2.2, Δ_{k−1}T (n) ∈ { 0, k−1 }; and by induction, Δ_{k−1−d}T (n−d) ∈ { 0, k−1 }. Therefore, |Δ_{d}T (n)| ∈ { 0, k − 1 }. We need to rule out the case Δ_{d}T (n) = 1 − k. We expand Δ_{d}T (n) as a telescoping sum:

(5.2) Δ_{d}T (n) = ∑_{{i even \atop ∈[0,d)}} Δ_{2}T (n − i).

By induction, when i > 0, Δ_{2}T (n − i) ∈ { 0, k − 1 }. To prove that Δ_{d}T (n) ≥ 0, it therefore suffices to show that the first summand Δ_{2}T (n) ≥ 0, that is, Δ_{2}T (n) ≠ 1 − k. Write

(5.3) Δ_{2}T (n) = Δ_{k−1}T (n) − Δ_{k−3}T (n − 2).

We will assume that Δ_{2}T (n) = 1 − k and show that a contradiction ensues. From Equation (5.3) it follows that 0 = Δ_{k−1}T (n) and k − 1 = Δ_{k−3}T (n − 2). But Δ_{k−3}T (n − 2) = Δ_{k−1}T (n − 2) − Δ_{2}T (n − k + 1), and by the same reasoning 0 = Δ_{2}T (n − k + 1), which will be contradicted below.

By Lemma 4.1, 1 − k = Δ_{2}T (n) = Δ_{k}U(n) + Δ_{k}U(n − 1) = Δ_{k+1}U(n) + Δ_{k−1}U(n − 1) = Δ_{2}U(n) + Δ_{k−1}U(n − 2) + Δ_{k−1}U(n − 1). Since by Proposition 2.2 the last two terms are nonnegative, Δ_{2}U(n) = 1 − k. Δ_{2}R(n) = 2 − Δ_{2}T (n − 1) ∈ { 2, 3 − k } by induction; but if it were 2 then Δ_{2}U(n) would be equal to (Δ_{2}T)(R(n)) ∈ { 0, k−1 } contradicting our earlier assumption. Thus Δ_{2}T (n−1) = k − 1 and Δ_{2}R(n) = 3 − k. By Equation (5.2), Δ_{k−1}T (n − 1) = k − 1.

So Δ_{k−1}T (n−1)−Δ_{k−1}T (n) = (k −1)−0 and if we expand this using Equation (5.1) and gather terms; k − 1 = Δ_{k−1}U(n − k) − Δ_{k−1}U(n) and by Proposition 2.2, k − 1 = Δ_{k−1}U(n − k). By Corollary 2.5, Equation (5.1) and the properties of the difference operator (respectively), 0 = ∑_{i=k+1}^{2k} Δ_{k−1}U(n−i) = Δ_{k−1}T (n−k −1) = Δ_{k−3}T (n − k − 1) + Δ_{2}T (n − 2k + 2), both of whose last terms are thus zero; while by Equation (1.6), k − 1 ≥ Δ_{k−1}T (n − k + 1) ≥ Δ_{k−1}U(n − k) = k − 1.

But then Δ_{2}T (n − k + 1) = Δ_{k−1}T (n − k + 1) − Δ_{k−3}T (n − k − 1) = k − 1, a contradiction. Thus, Δ_{2}T (n) ∈ { 0, k − 1 } and the induction is complete. □

The polypaeon structure can be viewed as arising from the difference identity

(5.4) Δ_{k+1}Δ_{k−1}U(n) = Δ_{k−1}Δ_{k+1}U(n)

This elementary difference equation causes periodicity with period k ± 1 in the sequences Δ_{k∓1}U(n) to mutually reinforce each other: Δ_{k−1}U(n) is periodic with period k + 1 on an interval (i.e., the left side of Equation (5.4) is zero) if and only if Δ_{k+1}U(n) is periodic on that interval with period k − 1 (i.e., the right side of Equation (5.4) is zero).

Recall Note 2.1, which lists values of Δ_{6}U(n) when k = 7. We can now recognize the values beginning with n = 15 as forming three paeons, then a hypercatalectic, then seven more paeons. Δ_{6}U(n) is therefore periodic with period 8 on the interval from n = 15 to n = 38, and again from n = 40 to n = 95. That means that according to Equation (5.4), Δ_{8}U(n), whatever its values may be, is periodic with period six on those two ranges of n. The reader may verify that in fact Δ_{8}U(n) = 0, except at the beginning of each period, when it is equal to 6.

For general odd k, we will show that the periods in Δ_{k+1}U(n) behave similarly to the case k = 7: the difference sequence is 0 except at the beginning of each period of length k − 1, where it has the value k − 1. So we have two difference sequences, Δ_{k−1}U(n) and Δ_{k+1}U(n) which are mostly zero, but almost periodically equal to k − 1 (with different periods). In that follows, we will need to discuss the phase difference between these sequences, which we now define.

Definition 5.3. Let n mark the beginning of a paeon in Δ_{k−1}U(n), that is, φ(n) = P. The phase difference θ(n) between the sequences Δ_{k±1}U(n) is the smallest nonnegative value for which Δ_{k+1}U(n + θ(n)) ≠ 0.

Since the periods in Δ_{k+1}U are shorter than the periods in Δ_{k−1}U by two, the phase difference θ(n) decreases by two (modulo k − 1) with each successive consecutive paeon in Δ_{k−1}U. We will also find that because of the way in which the periodicity in the two difference sequences is mutually reinforcing, the only time that a hypercatalectic can occur in Δ_{k−1}U is when the phase difference is about to drop from two to zero, θ(n) returns to zero at the beginning of each polypaeon and Δ_{k+1}U(n) is zero except where it is k − 1. We will use these ideas in the following proof of the polypaeon structure of Δ_{k−1}U(n), which while lengthy illustrates well the added complexity of the case of general odd k.

Proposition 5.4 (Polypaeon Structure of Δ_{k−1}U(n)).

(I) Along each polypaeon, Δ_{k+1}U consists of \frac{k+1}{2} copies of the k − 1 integers (k − 1, 0,…, 0). Formally, suppose φ(n) = P marks the start of a polypaeon, and n ≤ m < n + \frac{k^{2}−1}{2}. Then Δ_{k+1}U(m) = k − 1 if m ≡ n (mod k − 1), and Δ_{k+1}U(m) = 0 otherwise.

(II) At a hypercatalectic, Δ_{k+1}U vanishes. Formally, if φ(n) = H, then we have Δ_{k+1}U(n) = 0.

(III) Polypaeons are followed either by polypaeons or hypercatalectics. Formally, if φ(n − \frac{k^{2}−1}{2}) = P marks the start of a polypaeon, then that polypaeon is followed at n by either another polypaeon or a hypercatalectic.

(IV) Hypercatalectics are followed by polypaeons. Formally, if φ(n − 1) = H, then a polypaeon starts at n.

Proof. It is laborious, but not difficult, to verify directly that there is a polypaeon which starts at 2k + 1 and is followed by a hypercatalectic at \frac{1}{2}(k^{2} + 4k + 1), along both of which Δ_{k+1}U has the required values.

We proceed by induction, assuming that all four statements hold for all lesser n. In what follows, we will use statements (I) and (II) to compute values of Δ_{k+1}U that precede n, and use statements (III), (IV) and the abovementioned presence of the initial polypaeon starting at 2k + 1 and hypercatalectic at \frac{1}{2}k^{2} + 4k + 1 to ensure the polypaeon-hypercatalectic structure that immediately precedes n. We begin by proving statement (I).

By Equation (5.4) on the commutativity of the difference operator, Δ_{k+1}U(n) = Δ_{k+1}U(n−k+1)+Δ_{k−1}U(n)−Δ_{k−1}U(n−k−1). By induction, Δ_{k+1}U(n−k+1) = Δ_{k−1}U(n−k−1), with both being equal to zero if n is preceded by a hypercatalectic, and being equal to k − 1 if n is preceded by a paeon. Δ_{k−1}U(n) = k − 1 by assumption, so Δ_{k+1}U(n) is also equal to k − 1. The rest of statement (I) follows by induction (to obtain earlier values of Δ_{k+1}U) and the periodicity that Equation (5.4) and the repeated paeons in the polypaeon impose on Δ_{k+1}U.

Proving statement (II) simply consists of using (5.4) and induction to compute Δ_{k+1}U(n) = Δ_{k+1}U(n − k + 1) + Δ_{k−1}U(n) − Δ_{k−1}U(n − k − 1) = 0 + 0 − 0 = 0.

Statement (III) is more difficult to prove. It follows directly from Corollary 2.5 and Definition 5.1 that what follows the last paeon of a polypaeon must either be a hypercatalectic (if Δ_{k−1}U(n) = 0) or a paeon (if Δ_{k−1}U(n) = k − 1). We assume therefore the latter case. It is not obvious at the outset that the paeon at n is the first paeon of a full polypaeon. We will prove that this in fact true by showing (i) that θ(n) = 0, (ii) that θ drops by two modulo k − 1 with each successive paeon, and (iii) that the only time the next hypercatalectic can occur is when θ would drop from two to zero.

In our proof above of statement (I), we showed that φ(n) = P implies that Δ_{k+1}U(n) = k − 1, and showed how to use periodicity to calculate the values of Δ_{k+1}U(n) that are induced by consecutive paeons, showing (ii). Since Δ_{k+1}U(n) = k −1, we have θ(n) = 0. And since the (k −1)s in Δ_{k+1}U recur with period k −1 as long as we continue to have consecutive paeons at n′ ∈ {n, n+k+1, n+2(k+1),… }, then θ(n′) drops by two modulo k − 1 with each successive paeon.

To obtain (iii), we need to determine whether the next foot after the paeon at some n′ is a paeon or a hypercatalectic. We calculate:

(5.5) Δ_{k−1}U(n′ + k + 1) = 0 + … + 0 + Δ_{k−1}U(n′ + k + 1)

= ∑_{i=0}^{k−1} Δ_{k−1}U(n′ + k + 1 − i)

= Δ_{k−1}T (n′ + k + 1)

= ∑_{0≤j even<k−1} Δ_{2}T (n′ + k + 1 − j), by (5.2).

If θ(n′) > 2, then Δ_{2}T (n′ + θ(n′)) is one of these summands, which we can then compute as follows.

(5.6) Δ_{2}T (n′ + θ(n′)) = ∑_{i=0}^{k−1} Δ_{2}U(n′ + θ(n′) − i), which telescopes to
= Δ_{k+1}U(n′ + θ(n′)) + Δ_{k−1}U(n′ + θ(n′) − 1)
= (k − 1) + 0 = k − 1.

It is worth noting in passing that Equation (5.6) shows that Δ_{2}T (n′) = k − 1 whenever Δ_{k+1}U(n′) = k − 1.

We now consider three cases separately: θ(n′) > 2, θ(n′) = 0 and θ(n′) = 2. In the first case, if θ(n′) > 2, then Equation (5.6) shows that Δ_{k−1}U(n′+k+1) =

k − 1 starts a paeon.

In the second case, if θ(n′) = 0, then by the same argument used in the proof of (I) above, Δ_{k+1}U(n′ + k − 1) = k − 1. And by the same argument used in Equation (5.6), substituting k − 1 for θ(n′), we have Δ_{2}T (n′ + k − 1) = k − 1. This value of Δ_{2}T is among the summands in the last line of Equation (5.5), so Δ_{k−1}U(n′ + k + 1) = k − 1 begins a paeon.

It is therefore only in the third case, θ(n′) = 2, that a hypercatalectic can occur. This completes the proof of statement (III). All that remains now is statement (IV).

We know from Proposition 2.2 that Δ_{k−1}U(n) is either 0 or k−1. If Δ_{k−1}U(n) = k − 1, then we can use the preceding proof of statement (III) to show that it marks the beginning of a polypaeon. What we need to show then is simply that Δ_{k−1}U(n) ≠ 0.

To do so, we generalize the proof of Proposition 3.3, relying on the polypaeon property to ensure that the number of preceding paeons is a multiple of \frac{k−1}{2}, so that we can compute some key differences of T.

By induction and the presence of a first hypercatalectic at n = \frac{1}{2}k^{2} + 4k + 1, we know that the hypercatalectic at n − 1 is preceded by some positive number of polypaeons, the first of which is itself preceded by a hypercatalectic. For some positive q = r \frac{k−1}{2} then, Δ_{k−1}U(n − k − 2) = Δ_{k−1}U(n − 2(k + 1) − 1) = … = Δ_{k−1}U(n−q(k +1)−1) = Δ_{k−1}U(n−(q +1)(k +1)−2) = k −1 and Δ_{k−1}U(i) = 0 for all other i in the interval [n − (q + 1)(k + 1) − 2, n − 1].

Use these known values of Δ_{k−1}U, the distributivity of the difference operator over the definition of T in Equation (5.1) and the equation Δ_{d}R(n) = d−Δ_{d}T (n−1) to compute four important differences of R.

(5.7) Δ_{2}R(n) = 2 − Δ_{2}T (n − 1)

= 2 − Δ_{k+1}T (n − 1) + Δ_{k−1}T (n − 3)

= 2 − ∑_{i=0}^{k−1} Δ_{k+1}U(n − 1 − i) + ∑_{i=0}^{k−1} Δ_{k−1}U(n − 3 − i)

= 2 − (k − 1) + (k − 1) = 2

The preceding sums are evaluated by using induction to find the values of the differences of U and observing that exactly one summand in each range is nonzero. The following three equations are derived similarly, using in addition a parity argument for equation (5.10).

(5.8)  Δ_{k−1}R(n) = k − 1

(5.9) Δ_{k−1}R(n − q(k + 1) − 2) = k − 1
(5.10) Δ_{k−1}R(n − i(k − 1) − 2) = 0, for 0 ≤ i ≤ r \frac{k + 1}{2}

By definition, Δ_{k−1}U(n) = U(n) − U(n − k + 1) = T (R(n)) − T (R(n − k + 1)). Since Δ_{k−1}R(n) = k−1, we can continue the equation T (R(n))−T (R(n−k+1)) = T (R(n))−T (R(n)−k +1) = (Δ_{k−1}T)(R(n)) = ∑_{i=0}^{k−1}(Δ_{k−1}U)(R(n)−i). We need to show that this last sum is equal to k − 1. We claim that this is so because one of its first two terms is k − 1 and the rest are all zero. By the inductive assumption that the sequence preceding n consists of feet, it suffices to show that (Δ_{k−1}U)(R(n) − i) = 0 for i ∈ [2, k + 1], forcing one of the two following differences (i = 0 or i = 1) of U to be the nonzero start of a paeon.

∑_{i=2}^{k+1}(Δ_{k−1}U)(R(n) − i) = (Δ_{k−1}T)(R(n) − 2)

= (Δ_{k−1}T)(R(n − 2)), by (5.7)

= (Δ_{k−1}T)(R(n − r \frac{k + 1}{2}(k − 1) − 2)), by (5.10)

= (Δ_{k−1}T)(R(n − q(k + 1) − 2))

= (Δ_{k−1}U)(n − q(k + 1) − 2), by (5.9)

= 0

All the summands are therefore zero, and so one of (Δ_{k−1}U)(R(n) − 1) and (Δ_{k−1}U)(R(n)) must be k − 1 and we are done. □

The fundamental result that Δ_{k−1}U consists of polypaeons separated by at most one zero (constituting a hypercatalectic) now follows as a direct consequence.

Corollary 5.5. (A generalized version of Proposition 3.3.) {Δ_{k−1}U(n)}_{n=2k+1}^{∞} consists only of feet, and each of its paeons occurs within a run of polypaeons.

Proof. Follows immediately from Proposition 5.4. □

Since the remainder of the results in this section may be proven by straightforward generalizations of the corresponding earlier propositions, we state them here without proof.

Theorem 5.6. (A generalized version of Foot Pattern Theorem 3.4.) Suppose the parameters n_{0}, t_{0},…, t_{k−2}, r_{0},…, r_{k−2} and d satisfy all of the following conditions: n_{0} ≥ 2k + 1, Δ_{k−1}U(n_{0}) = k − 1, Δ_{k−1}U(n_{0} + k + 1) = d, and for 0 ≤ i ≤ k − 2, T (n_{0} + i) = t_{i}, and R(n_{0} + i) = r_{i}. Then T (n), Δ_{k−1}T (n), R(n), Δ_{k−1}R(n), Δ_{k−1}U(n) and φ(n) have the values shown in Table 5.1.

Definition 5.7 (Generation). For any g > 0, let m_{g} := \frac{1}{k−1}(k^{g+1} +k^{2} −k −1) = k + ∑_{i=0}^{g} k^{i} and call the interval [m_{g}, m_{g+1} − 1] the gth generation, written gen(g). We partition the gth generation into two nonconsecutive subsequences: the gth even semigeneration sg_{0}(g) := { n ∈ gen(g) | n ≡ m_{g} (mod 2) } and the gth odd semigeneration sg_{1}(g) := { n ∈ gen(g) | n ≢ m_{g} (mod 2) }. For any sequence s(n), we will refer to the subsequence { s(n) | n ∈ gen(g), s(n) defined } as the gth generation of s and similarly for semigenerations. An even (odd) foot is one that starts in an even (odd) semigeneration. Note that because the length k^{g+1} of gen(g) is odd, m_{g} and m_{g+1} always have opposite parity.

n  T(n) Δ_{k−1}T(n) R(n) Δ_{k−1}R(n) Δ_{k−1}U(n) φ(n)
n_{0} − k  t_{k−2} − k + 1 k − 1  ?  0  0  −
n_{0} − k + 1 t_{0} − k + 1 k − 1 r_{0} − k + 1  0  0  −
⋮  ⋮  ⋮  ⋮  ⋮  ⋮  ⋮
n_{0} − 3  t_{k−4} − k + 1 k − 1  ?  0  0  −
n_{0} − 2  t_{k−3} − k + 1  ?  r_{0} − 2  0  0  −
n_{0} − 1  t_{k−2} − k + 1  0  r_{1}  ?  0  ?
n_{0}  t_{0}  k − 1  r_{0}  k − 1  k − 1  P
n_{0} + 1  t_{1}  k − 1  r_{1}  0  0  −
⋮  ⋮  ⋮  ⋮  ⋮  ⋮  ⋮
n_{0} + k − 2  t_{k−2}  k − 1  r_{k−2}  0  0  −
n_{0} + k − 1 t_{0} + k − 1 k − 1  r_{0}  0  0  −
n_{0} + k  t_{1}  0  r_{1}  0  0  −
n_{0} + k + 1  t_{2} + d  d  r_{2} + k − 1  k − 1  d  P or H
n_{0} + k + 2 t_{3} + k − 1 k − 1  {r_{3}+ \atop k−1−d}  k − 1 − d k − 1 − d − or P
n_{0} + k + 3 t_{4} + k − 1 k − 1  r_{4}  0  0  −

Table 5.1: Function Values Over a Paeon for Odd k

Theorem 5.8. (A generalized version of Generation Pattern Theorem 3.15.) The gth generation of Δ_{k−1}U consists entirely of k^{g} feet, which make up k^{g−1} + 1 lines. Its last line consists only of (odd) paeons, the last of which has Foot Pattern Theorem 5.6 parameters n_{0} = m_{g+1} − k − 1, t_{0} = k^{g+1} − k + 1, t_{1} = … = t_{k−2} = k^{g+1}, r_{0} = m_{g} − 2, r_{1} = m_{g} − 1 and for 2 ≤ i ≤ k − 2, r_{i} = m_{g} + i − 2.

At this point, we have generalized all of Section 3 for odd k, describing the generational structure of the sequences. The remaining results in this section generalize the indicated propositions and theorems about properties of the sequences, proven for k = 3 in Section 4.

Proposition 5.9. (A generalized version of Proposition 4.10.) The sequence consisting of the number of paeons in each even line in the (g + 1)st generation of Δ_{2}U is:

\{ \frac{k + 1}{2} q_{0,g}, \overbrace{\frac{k − 1}{2}, …, \frac{k − 1}{2}}^{q_{1,g}},…, \frac{k + 1}{2} q_{k^{g−1}−1,g}, \overbrace{\frac{k − 1}{2}, …, \frac{k − 1}{2}}^{q_{k^{g−1},g}} \}.

Theorem 5.10. (A generalized version of Theorem 4.11.) Each generation of the sequence Δ_{k−1}U(n) consists of a palindromic sequence of feet.

Proposition 5.11. (A generalized version of Proposition 4.13.) q_{i,g} is always \frac{k−1}{2} times a power of \frac{k+1}{2}.

Proposition 5.12. (A generalized version of Proposition 4.14.) For positive g and 0 ≤ x ≤ m_{g+1} − k − 1, the sum T (m_{g} + x) + T (m_{g+1} − k − 1 − x) = k^{g} + k^{g+1} is constant. For 0 ≤ y ≤ m_{g+1}−2k, the sum U(m_{g}+y)+U(m_{g+1}−2k−y) = k^{g−1}+k^{g} is constant.

Proposition 5.13. (A generalized version of Proposition 4.15.) The mean value of the gth generation of T (n) is \frac{1}{2}(k^{g+1} + k^{g} + k − 1).

Corollary 5.14. (A generalized version of Corollary 4.16.) The asymptotic value of \frac{T (n)}{n} is \frac{k−1}{k}.

Proposition 5.15. (A generalized version of Proposition 4.17.) The mean value of the gth generation of Δ_{2}T (n) is \frac{2(k−1)}{k}. The mean value of the gth generation of Δ_{2}U(n) is \frac{2(k−1)}{k^{2}}.

We conclude this section with a few conjectures based on empirical evidence. This paper does not for the most part discuss the case of a ≠ 0, but the following observation seems closely enough related to the palindromicity property proven in Section 4 to be worth mentioning here.

Conjecture 5.16. (A generalized version of Proposition 4.11.) For general a and odd k, Δ_{k−1}U has a palindromic generational structure, but there are k extra zeroes after each generation.

We have observed the following curious property, which describes a surprising way in which the even and odd q sequences dovetail together.

Conjecture 5.17. For a = 0, odd k and sufficiently large g, the number of consecutive times that q_{i,g} has the value \frac{k−1}{2} is always k.

As in the case of k = 3, maximal runs of identical values in the T (n) sequence tend to occur at the ends of generations. This appears to be true for any odd k.

Conjecture 5.18. (A generalized version of Theorem 4.3.) For a = 0 and odd k, T (n − k) = … = T (n − 1) if and only if n = m_{g} for some g.

We conclude this section with two open questions suggesting avenues for further research, and welcome correspondence concerning them.

Question 5.19. What can be said of the sequences generated by other initial values? In particular, which initial values give sequences which are well-defined, and which ones lead to a generational structure of the sort described in this paper?

Question 5.20. Let a = 0 and k be odd. The palindromic symmetry property means that the values of each sequence at odd integers can be simply expressed in terms of the values at even integers, and vice versa. Is there a simple recurrence for T (2n) in terms of T at other even integers?

6. Conjectures for Even k

Figure 6.1 shows T_{0,4}(n) with the usual initial values (1, 1, 1, 1). Unlike when k is odd, we do not see a bifurcation into two intertwined subsequences; rather, the sequence stays close to the expected line T = \frac{3}{4}n.

150 100 50  \begin{matrix}n \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \end{matrix} ^{\begin{matrix}T (n) \\ 1 \\ 1 \\ 1 \\ 1 \\ 4 \\ 4 \\ 4 \\ 4 \\ 7 \\ 7 \\ 7 \\ 10 \end{matrix} \begin{matrix}n \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \\ 23 \\ 24 \end{matrix}} \begin{matrix}T (n) \\ 7 \\ 10 \\ 13 \\ 10 \\ 13 \\ 13 \\ 13 \\ 16 \\ 16 \\ 16 \\ 16 \\ 16 \end{matrix} 0
0  50  100  150  200

Figure 6.1: T_{0,4}(n) with initial values (1, 1, 1, 1)

Nonetheless, because of Corollary 2.5, we know that the sequence Δ_{3}U_{0,4}(n) has a block structure of runs of paeons separated by one or more zeroes (resembling hypercatalectics). These zeroes can appear singly or (unlike when k is odd) multiply: there are two zeroes in a row at n = 87 and n = 88 following the paeon that runs from n = 82 to n = 86. Still, if we make a minor change in our definition of feet to allow for consecutive hypercatalectics, we can define feet, lines and generations in a natural way that fits our empirical observations.

Definition 6.1. Let a = 0 and k be even. A paeon is a sequence \{ k − 1, \overbrace{0,…, 0}^{k} \} of k + 1 consecutive values of Δ_{k−1}U(n). A hypercatalectic is a singleton sequence { 0 }, in {Δ_{k−1}U(n)} that is not part of a paeon. A foot is either a paeon or a hypercatalectic. For convenience, we will write { P } interchangeably with the paeon { k−1, 0,…, 0 } and likewise { H } with the hypercatalectic { 0 } when listing values of Δ_{k−1}U. We also define φ(n) as the symbol P if Δ_{k−1}U(n) = k − 1 begins a paeon, H if Δ_{k−1}U(n) = 0 is a hypercatalectic, and leave it undefined otherwise. For any g > 0, let m_{g} := \frac{1}{k−1}(k^{g+1} + k^{2} − k − 1) = k + ∑_{i=0}^{g} k^{i} and call the interval [m_{g}, m_{g+1} − 1] the gth generation, written gen(g). For any sequence s(n), we will refer to the subsequence { s(n) | n ∈ gen(g), s(n) defined } as the gth generation of s and similarly for semigenerations. An even (odd) foot is one that starts in an even (odd) semigeneration.

We say that this definition is a natural one, because it allows some of the sequence properties we observed earlier for odd k to continue to hold for even k. For example, there is always a run of equal values of T (n) at the end of each generation, as can be seen in Figure 6.1 preceding n = m_{2} = 25 and n = m_{3} = 89.

In light of this definition, it is instructive to look back at the case k = 2 (Conolly’s sequence), which is completely understood, in light of this definition. In its corresponding Δ_{1}U sequence, beginning with the second generation at n = m_{2} = 9, paeons always occur in pairs, and the number of consecutive hypercatalectics that occur between pairs of paeons forms the previously mentioned Gray binary sequence 1, 2, 1, 3, 1, 2, 1, 4,…, with an extra hypercatalectic at the end of each generation.

We believe that all of Section 3 can be generalized to even k. We do not however observe palindromic symmetry or polypaeon structure, so not all of Section 4 can be carried over to this case. For example, when k = 4, the first generation of Δ_{2}U consists of the feet {P, P, P, H}; the second generation is {P, P, P, P, P, H, P, P, P, P, P, H, P, P, H, H}; the third generation begins with a copy of the second generation, includes a run of eight paeons, and ends with three consecutive hypercatalectics. None of the generations are palindromic, and consecutive paeons appear in varying and relatively prime numbers.

The following four conjectures state how we believe our results of Section 3 will generalize to even k, based on empirical evidence.

Conjecture 6.2. For a = 0, even k, and the usual initial conditions T_{0,k}(n) = 1 for 1 ≤ n ≤ k, implicitly define f(R(n)) := n for n ∈ Dom φ. Then f is well-defined on its domain and f(r) is the least n for which r = R(n).

Conjecture 6.3. (A generalized version of Foot Pattern Theorem 5.6.) Let a = 0, k be even, and assume the usual initial conditions T_{0,k}(n) = 1 for 1 ≤ n ≤ k. Suppose the parameters n_{0}, t_{0},…, t_{k−2}, r_{0},…, r_{k−2} and d satisfy all of the following conditions: n_{0} ≥ 2k + 1, Δ_{k−1}U(n_{0}) = k − 1, Δ_{k−1}U(n_{0} + k + 1) = d, and for 0 ≤ i ≤ k − 2, T (n_{0} + i) = t_{i}, and R(n_{0} + i) = r_{i}. Then T (n), Δ_{k−1}T (n), R(n), Δ_{k−1}R(n), Δ_{k−1}U(n) and φ(n) have the values shown in Table 5.1.

Conjecture 6.4. (A generalized version of Generational Correspondence Theorem 3.14.) Let a = 0 and k be even. Then the diagram

Dom f \overrightarrow{⟵}_{R}^{f} Ran f
Δ_{k−1}T ↓  ^{φ}↓
{0, k − 1} ⟶_{k−1↦P}^{0↦H} {H, P }

commutes. That is, for k + 1 ≤ r ∈ Dom f, φ(f(r)) = P iff Δ_{k−1}T (r) = k − 1.

Conjecture 6.5. (A generalized version of Generation Pattern Theorem 3.15.) Let a = 0 and k be even. Then the gth generation of Δ_{k−1}U consists entirely of k^{g} feet, which make up k^{g−1} lines. The generation ends with g hypercatalectics preceded by a paeon, and if we let n_{0} := m_{g+1} − k − 1, then for 0 ≤ i ≤ k − 2, T (n_{0} + i) = k^{g+1} and R(n_{0} + i) = m_{g} − k − 1 + i.

While we do not have palindromic symmetry when k is even, the existence of f appears to be sufficient to generalize the following sequence property observed in Section 5.

Conjecture 6.6. (A generalized version of Proposition 5.15.) For a = 0 and any (not necessarily odd) k, the mean value of the gth generation of Δ_{2}T (n) is \frac{2(k−1)}{k}. The mean value of the gth generation of Δ_{2}U(n) is \frac{2(k−1)}{k^{2}}.

As in the case of odd k described in Conjecture 5.18, it is also true for even k that maximal runs of identical values in the T (n) sequence tend to occur at the ends of generations.

Conjecture 6.7. (A generalized version of Theorem 4.3.) For a = 0, even k and any g, T (m_{g+1} − k − g) = … = T (m_{g+1} − 1) and there are no earlier runs of k + g identical consecutive values of T (n).

In a forthcoming communication, we hope to resolve the above conjectures in the broader context of the determination of the complete structure of our sequences for even k.

References

1. Allenby, R.B.J.T and Smith, Rachel C., Some sequences resembling Hofstadter’s, J. Korean Math. Soc. 40 (2003), no. 6, 921–932.

2. Aristotle, Ars Rhetorica (Sir David Ross, ed.), Oxford University Press, Oxford, 1959, pp. 158-159, Bekker index 1409a.

3. Conolly, B.W., Meta-Fibonacci Sequences, Fibonacci & Lucas numbers, and the Golden Section (S. Vajda, ed.), John Wiley & Sons, New York, 1986, pp. 127–137.

4. Elzinga, Cees H., private communication (October 2001).

5. Higham, Jeff and Tanny, S., More well-behaved meta-Fibonacci sequences, Congr. Numer. 98 (1993), 3–17.

6. Higham, Jeff and Tanny, Stephen, A tamely chaotic meta-Fibonacci sequence., Congr. Numer. 99 (1994), 67–94.

7. Hofstadter, Douglas, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, New York, 1979.

8. Huber, Greg and Hofstadter, Douglas, private communication (1999).

9. Huber, Greg, private communication (May 2002).

10. Kubo, T. and Vakil, R., On Conway’s Recursive Sequence, Discrete Mathematics 152 (1996), no. 1-3, 225–252.

11. Lancashire, Ian, Glossary of Poetic Terms (Version 2.07), Representative Poetry Online (Version 2.11), http://www.library.utoronto.ca/utel/rp/intro.html, 1994.

12. Mallows, C.L., Conway’s Challenge Sequence, American Mathematical Monthly 98 (1991), no. 1, 5–20.

13. Sloane, N.J.A., Sloane’s Encyclopedia of Integer Sequences, http://www.research.att.com/ ∼njas/sequences.

14. Tanny, Stephen M., A well-behaved cousin of the Hofstadter sequence, Discrete Mathematics 105 (1992), 227-239.

Department of Mathematics, University of Toronto, Toronto, Ontario, Canada M5S 3G3

E-mail address: calaghan@math.utoronto.ca

Department of Mathematics, University of Toronto, Toronto, Ontario, Canada M5S 3G3

E-mail address: jjchew@math.utoronto.ca
URL: http://www.poslfit.com

Department of Mathematics, University of Toronto, Toronto, Ontario, Canada M5S 3G3

E-mail address: tanny@math.utoronto.ca