How the Shift Parameter Affects the Behavior of a Family of Meta-Fibonacci Sequences

Mu Cai and Stephen M. Tanny Department of Mathematics University Of Toronto Toronto, Ontario M5S 2E4 Canada

                tanny@math.toronto.edu

Abstract

We explore the effect of different values of the shift parameter s on the behavior of the family of meta-Fibonacci sequences defined by the k-term recursion

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

with the s + k initial conditions T_{s,k}(n) = 1 for 1 ≤ n ≤ s + k. We show that for any odd k ≥ 3 and non-negative integer s the values in the sequence T_{s,k}(n) and T_{0,k}(n) are essentially the same. The only differences in these sequences are that each power of k occurs precisely k + s times in T_{s,k}(n) and k times in T_{0,k}(n). For even k the frequency of k^{r} in T_{0,k}(n) depends upon r. We conjecture that for k even the effect of the shift parameter s is analogous to that for k odd, in the sense that the only differences in the sequences T_{s,k}(n) and T_{0,k}(n) occur in the frequencies of the powers of k; specifically, each power of k appears to occur precisely s more times in T_{s,k}(n) than it does in T_{0,k}(n).

1 Introduction

In this paper, unless otherwise indicated all values are integers. For s ≥ 0 and k ≥ 2 consider the generalized Conolly meta-Fibonacci (self-referencing) recursion defined in [2]:

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

For given values of the parameters s and k the behavior of the sequence defined by (1.1) is highly sensitive to the choice of the initial conditions. Some initial conditions lead to sequences with identifiable and regular (though potentially very complex) patterns, while others generate highly chaotic sequences or even cause the sequence T_{s,k}(n) eventually to fail to be defined; that is, for some value of n the argument of one of the terms on the right hand side of T_{s,k}(n) becomes negative. See [2] for additional details.

In the special case s = 1, and with the initial conditions T_{1,k}(1) := 1 and T_{1,k}(i) := i − 1, 2 ≤ i ≤ k + 1, the resulting sequence behaves in a very simple manner [7]. In particular, it is monotone and its consecutive terms increase by either 0 or 1, so it hits every positive integer. Following Ruskey [9] we term such a sequence “slowly growing”.

In [5] and [6] Ruskey and his colleagues derive a beautiful combinatorial interpretation in terms of k-ary trees for each of the sequences generated by (1.1) with k ≥ 2, s ≥ 0 and the initial conditions T_{s,k}(i) := 1 for 1 ≤ i ≤ s + 1 and T_{s,k}(s + i) := i, 2 ≤ i ≤ k. Using these initial conditions, which are a natural analogue for general s to the ones in [7] for s = 1, they show that for every k ≥ 2 all these sequences are slowly growing. Even further, from their combinatorial interpretation it is immediate that for fixed k the sequences T_{s,k}(n) and T_{s+1,k}(n) are essentially the same: the only differences in these sequences occur in the frequencies with which the powers of k occur. In particular, each power of k occurs precisely one more time in the sequence T_{s+1,k}(n) than it does in T_{s,k}(n). See Table 1 for examples of this for k = 3, 4, 5 and s = 0, 1, 2.

The shift parameter is known to have this benign type of effect on other families of slowing growing sequences that are generated by a meta-Fibonacci recursion similar to the one for T_{s,k}(n). See, for example, [1]. The focus of this paper is to show that the shift parameter s can have such a modest effect even when the behavior of the sequence is considerably more complicated.

We demonstrate this by showing it to be the case for the family of sequences generated by (1.1) but this time with a very different set of initial conditions, namely, T_{s,k}(n) = 1 for 1 ≤ n ≤ s + k. These sequences are introduced in [2], but only the special case s = 0 is analyzed in detail. They are not monotone and display considerably more complex behavior than that of the slowly growing sequences discussed in [5] and [6]. See Figures 1, 2 and 3. In [2] the structure of these sequences is completely described for s = 0 and k odd. In particular it is shown that the terms of the sequence T_{0,k}(n) that are equal to k^{r} for any non-negative integer r necessarily appear as a block of k consecutive terms. Table 2 illustrates this for k = 3 and s = 0; note the three consecutive occurrences of the values 3, 9, 27 and 81.

In this paper we extend the analysis in [2] by allowing arbitrary positive integer values for s. Specifically we prove that for any odd k ≥ 3 and any non-negative integer s the values in the sequence T_{s,k}(n) and T_{0,k}(n) are essentially the same. The only differences in these sequences are that each power of k occurs precisely k + s times in T_{s,k}(n) and k times in T_{0,k}(n). Tables 2, 3 and 4 following illustrate this for k = 3 and s = 0, 1 and 2.

0 20 40 60 80 100 120 0  20  40  60  80 100 120 140 160 T_{0,3}(n)  n

Figure 1: First 160 terms of T_{0,3}(n) with initial values (1,1,1)

0 20 40 60 80 100 120 0  20  40  60  80 100 120 140 160 T_{1,3}(n)  n

Figure 2: First 160 terms of T_{1,3}(n) with initial values (1,1,1,1)

0 20 40 60 80 100 120 0  20  40  60  80 100 120 140 160 T_{2,3}(n)  n

Figure 3: First 160 terms of T_{2,3}(n) with initial values (1,1,1,1,1)

The proof of this simply stated and intuitively intriguing result is highly technical and makes extensive use of the approaches and results in [2]. It relies upon a series of nested induction arguments that are essentially the same for any odd k. As such, we proceed slowly and in stages, initially providing the details for the special case k = 3, where they are easier to follow. In Section 2 we establish the base case s = 1, namely, the result holds for the pair of sequences T_{0,3}(n) and T_{1,3}(n). We complete the induction for the case k = 3 and general s in Section 3. In Section 4 we sketch the induction argument for general odd k.

In Section 5 we conclude with some brief observations about the situation for k even. Based upon substantial empirical evidence it appears that our result also holds for this case. However, unlike the situation for k odd, there is no starting point for an induction argument similar to the one we use below since to date nothing has been proved about the sequences T_{0,k}(n) for k even (but see [2] for some conjectures).

Table 1: First 75 terms of T_{s,k}(n), s = 0, 1, 2, k = 3, 4, 5, initial conditions T_{s,k}(i) = 1, 1 ≤ i ≤ s + 1 and T_{s,k}(s + i) = i, 2 ≤ i ≤ k.

k = 3  k = 4  k = 5
n/s  0  1  2  0  1  2  0  1  2
1  1  1  1  1  1  1  1  1  1
2  2  1  1  2  1  1  2  1  1
3  3  2  1  3  2  1  3  2  1
4  3  3  2  4  3  2  4  3  2
5  4  3  3  4  4  3  5  4  3
6  5  3  3  5  4  4  5  5  4
7  6  4  3  6  4  4  6  5  5
8  6  5  3  7  5  4  7  5  5
9  7  6  4  8  6  4  8  6  5
10  8  6  5  8  7  5  9  7  5
11  9  7  6  9  8  6  10  8  6
12  9  8  6  10  8  7  10  9  7
13  9  9  7  11  9  8  11  10  8
14  10  9  8  12  10  8  12  10  9
15  11  9  9  12  11  9  13  11  10
16  12  9  9  13  12  10  14  12  10
17  12  10  9  14  12  11  15  13  11
18  13  11  9  15  13  12  15  14  12
19  14  12  9  16  14  12  16  15  13
20  15  12  10  16  15  13  17  15  14
21  15  13  11  16  16  14  18  16  15
22  16  14  12  17  16  15  19  17  15
23  17  15  12  18  16  16  20  18  16
24  18  15  13  19  16  16  20  19  17
25  18  16  14  20  17  16  21  20  18
26  18  17  15  20  18  16  22  20  19
27  19  18  15  21  19  16  23  21  20
28  20  18  16  22  20  17  24  22  20
29  21  18  17  23  20  18  25  23  21
30  21  19  18  24  21  19  25  24  22
31  22  20  18  24  22  20  25  25  23
32  23  21  18  25  23  20  26  25  24
33  24  21  19  26  24  21  27  25  25
34  24  22  20  27  24  22  28  25  25
35  25  23  21  28  25  23  29  26  25
36  26  24  21  28  26  24  30  27  25
37  27  24  22  29  27  24  30  28  25
38  27  25  23  30  28  25  31  29  26
39  27  26  24  31  28  26  32  30  27
40  27  27  24  32  29  27  33  30  28
41  28  27  25  32  30  28  34  31  29
42  29  27  26  32  31  28  35  32  30
43  30  27  27  33  32  29  35  33  30
44  30  27  27  34  32  30  36  34  31
45  31  28  27  35  32  31  37  35  32
46  32  29  27  36  33  32  38  35  33
47  33  30  27  36  34  32  39  36  34
48  33  30  27  37  35  32  40  37  35
49  34  31  28  38  36  33  40  38  35
50  35  32  29  39  36  34  41  39  36
51  36  33  30  40  37  35  42  40  37
52  36  33  30  40  38  36  43  40  38
53  36  34  31  41  39  36  44  41  39
54  37  35  32  42  40  37  45  42  40
55  38  36  33  43  40  38  45  43  40
56  39  36  33  44  41  39  46  44  41
57  39  36  34  44  42  40  47  45  42
58  40  37  35  45  43  40  48  45  43
59  41  38  36  46  44  41  49  46  44
60  42  39  36  47  44  42  50  47  45
61  42  39  36  48  45  43  50  48  45
62  43  40  37  48  46  44  50  49  46
63  44  41  38  48  47  44  51  50  47
64  45  42  39  49  48  45  52  50  48
65  45  42  39  50  48  46  53  50  49
66  45  43  40  51  48  47  54  51  50
67  46  44  41  52  49  48  55  52  50
68  47  45  42  52  50  48  55  53  50
69  48  45  42  53  51  48  56  54  51
70  48  45  43  54  52  49  57  55  52
71  49  46  44  55  52  50  58  55  53
72  50  47  45  56  53  51  59  56  54
73  51  48  45  56  54  52  60  57  55
74  51  48  45  57  55  52  60  58  55
75  52  49  46  58  56  53  61  59  56

Table 2: First 160 terms of T_{0,3}(n) with initial values (1, 1, 1)

n  n  n  n
1  2  1  2  1  2  1  2
T (n + 0)  1  1  T (n + 40) 27 27 T (n + 80)  59 49 T (n + 120)  81  81
T (n + 2)  1  3  T (n + 42) 29 29 T (n + 82)  59 51 T (n + 122)  81  83
T (n + 4)  3  3  T (n + 44) 31 29 T (n + 84)  61 53 T (n + 124)  83  85
T (n + 6)  5  5  T (n + 46) 33 31 T (n + 86)  61 55 T (n + 126)  83  87
T (n + 8)  7  5  T (n + 48) 35 31 T (n + 88)  63 57 T (n + 128)  85  89
T (n + 10)  7  7  T (n + 50) 37 33 T (n + 90)  63 57 T (n + 130)  85  91
T (n + 12)  9  9  T (n + 52) 39 33 T (n + 92)  65 59 T (n + 132)  87  93
T (n + 14)  9  11 T (n + 54) 41 35 T (n + 94)  67 59 T (n + 134)  87  95
T (n + 16) 11 13 T (n + 56) 43 35 T (n + 96)  67 61 T (n + 136)  89  97
T (n + 18) 11 15 T (n + 58) 43 37 T (n + 98)  69 63 T (n + 138)  89  99
T (n + 20) 13 17 T (n + 60) 45 39 T (n + 100) 69 63 T (n + 140)  91  101
T (n + 22) 13 17 T (n + 62) 45 39 T (n + 102) 71 65 T (n + 142)  91  103
T (n + 24) 15 19 T (n + 64) 47 41 T (n + 104) 73 65 T (n + 144)  93  105
T (n + 26) 17 19 T (n + 66) 49 41 T (n + 106) 73 67 T (n + 146)  93  107
T (n + 28) 17 21 T (n + 68) 49 43 T (n + 108) 75 69 T (n + 148)  95  109
T (n + 30) 19 23 T (n + 70) 51 45 T (n + 110) 75 71 T (n + 150)  95  111
T (n + 32) 19 23 T (n + 72) 51 45 T (n + 112) 77 73 T (n + 152)  97  113
T (n + 34) 21 25 T (n + 74) 53 47 T (n + 114) 77 75 T (n + 154)  97  113
T (n + 36) 23 25 T (n + 76) 55 47 T (n + 116) 79 77 T (n + 156)  99  115
T (n + 38) 25 27 T (n + 78) 55 49 T (n + 118) 79 79 T (n + 158) 101 115

Table 3: First 160 terms of T_{1,3}(n) with initial values (1, 1, 1, 1)

n  n  n  n
1  2  1  2  1  2  1  2
T (n + 0)  1  1  T (n + 40)  25  25  T (n + 80)  55  47  T (n + 120)  79  77
T (n + 2)  1  1  T (n + 42)  27  27  T (n + 82)  57  49  T (n + 122)  79  79
T (n + 4)  3  3  T (n + 44)  27  27  T (n + 84)  59  49  T (n + 124)  81  81
T (n + 6)  3  3  T (n + 46)  29  29  T (n + 86)  59  51  T (n + 126)  81  81
T (n + 8)  5  5  T (n + 48)  31  29  T (n + 88)  61  53  T (n + 128)  83  83
T (n + 10)  7  5  T (n + 50)  33  31  T (n + 90)  61  55  T (n + 130)  85  83
T (n + 12)  7  7  T (n + 52)  35  31  T (n + 92)  63  57  T (n + 132)  87  85
T (n + 14)  9  9  T (n + 54)  37  33  T (n + 94)  63  57  T (n + 134)  89  85
T (n + 16)  9  9  T (n + 56)  39  33  T (n + 96)  65  59  T (n + 136)  91  87
T (n + 18)  11  11  T (n + 58)  41  35  T (n + 98)  67  59  T (n + 138)  93  87
T (n + 20)  13  11  T (n + 60)  43  35  T (n + 100)  67  61  T (n + 140)  95  89
T (n + 22)  15  13  T (n + 62)  43  37  T (n + 102)  69  63  T (n + 142)  97  89
T (n + 24)  17  13  T (n + 64)  45  39  T (n + 104)  69  63  T (n + 144)  99  91
T (n + 26)  17  15  T (n + 66)  45  39  T (n + 106)  71  65  T (n + 146)  101  91
T (n + 28)  19  17  T (n + 68)  47  41  T (n + 108)  73  65  T (n + 148)  103  93
T (n + 30)  19  17  T (n + 70)  49  41  T (n + 110)  73  67  T (n + 150)  105  93
T (n + 32)  21  19  T (n + 72)  49  43  T (n + 112)  75  69  T (n + 152)  107  95
T (n + 34)  23  19  T (n + 74)  51  45  T (n + 114)  75  71  T (n + 154)  109  95
T (n + 36)  23  21  T (n + 76)  51  45  T (n + 116)  77  73  T (n + 156)  111  97
T (n + 38)  25  23  T (n + 78)  53  47  T (n + 118)  77  75  T (n + 158)  113  97

Table 4: First 160 terms of T_{2,3}(n) with initial values (1, 1, 1, 1, 1)

n  n  n  n
1  2  1  2  1  2  1  2
T (n + 0)  1  1  T (n + 40)  21  25  T (n + 80)  51  45  T (n + 120)  77  73
T (n + 2)  1  1  T (n + 42)  23  25  T (n + 82)  53  47  T (n + 122)  77  75
T (n + 4)  1  3  T (n + 44)  25  27  T (n + 84)  55  47  T (n + 124)  79  77
T (n + 6)  3  3  T (n + 46)  27  27  T (n + 86)  57  49  T (n + 126)  79  79
T (n + 8)  3  3  T (n + 48)  27  27  T (n + 88)  59  49  T (n + 128)  81  81
T (n + 10)  5  5  T (n + 50)  29  29  T (n + 90)  59  51  T (n + 130)  81  81
T (n + 12)  7  5  T (n + 52)  31  29  T (n + 92)  61  53  T (n + 132)  81  83
T (n + 14)  7  7  T (n + 54)  33  31  T (n + 94)  61  55  T (n + 134)  83  85
T (n + 16)  9  9  T (n + 56)  35  31  T (n + 96)  63  57  T (n + 136)  83  87
T (n + 18)  9  9  T (n + 58)  37  33  T (n + 98)  63  57  T (n + 138)  85  89
T (n + 20)  9  11  T (n + 60)  39  33  T (n + 100)  65  59  T (n + 140)  85  91
T (n + 22)  11  13  T (n + 62)  41  35  T (n + 102)  67  59  T (n + 142)  87  93
T (n + 24)  11  15  T (n + 64)  43  35  T (n + 104)  67  61  T (n + 144)  87  95
T (n + 26)  13  17  T (n + 66)  43  37  T (n + 106)  69  63  T (n + 146)  89  97
T (n + 28)  13  17  T (n + 68)  45  39  T (n + 108)  69  63  T (n + 148)  89  99
T (n + 30)  15  19  T (n + 70)  45  39  T (n + 110)  71  65  T (n + 150)  91  101
T (n + 32)  17  19  T (n + 72)  47  41  T (n + 112)  73  65  T (n + 152)  91  103
T (n + 34)  17  21  T (n + 74)  49  41  T (n + 114)  73  67  T (n + 154)  93  105
T (n + 36)  19  23  T (n + 76)  49  43  T (n + 116)  75  69  T (n + 156)  93  107
T (n + 38)  19  23  T (n + 78)  51  45  T (n + 118)  75  71  T (n + 158)  95  109

2 The behavior of T_{1,3}(n)

Consider the recursion (1.1) with k = 3 and s = 0 with initial conditions T (1) = T (2) = T (3) = 1:

T (n) = T (n − T (n − 1)) + T (n − 1 − T (n − 2)) + T (n − 2 − T (n − 3))  (2.1)

For convenience throughout this paper we omit either or both of the subscripts s and k where this causes no confusion. Following [2] we define U(n) = T (n − T (n − 1)), so T (n) = U(n) + U(n − 1) + U(n − 2). We determine bounds on U(n).

As in Definition 3.5 in [2], for any g > 0 call the interval (of the domain of the sequence) [m_{g}, m_{g+1} − 1] the g^{th} generation of the sequence T (n), written as gen(g), where m_{g} = \frac{1}{2}(3^{g+1} + 5). See Figure 4. Notice that the value of T (n) at the endpoints of each generation are powers of 3.

0 20 40 60 80 100 120 0  20  40  60  80 100 120 140 160 T_{0,3}(n)  n 1st generation 2nd generation 3rd generation 4th generation

Figure 4: Initial portion of generation structure of T_{0,3}(n)

Lemma 2.1. Let 2 ≤ g, and suppose that n is in the (g−1)^{th} generation, i.e. n ∈ [m_{g−1}, m_{g}− 1] = [(\frac{1}{2})3^{g} + \frac{5}{2}, (\frac{1}{2})3^{g+1} + \frac{3}{2}]. Then 3^{g−2} ≤ U(n), U(n − 1), U(n − 2) ≤ 3^{g−1}. Moreover U(m_{g} − 1) = U(m_{g} − 2) = U(m_{g} − 3) = 3^{g−1}.

Proof. From Theorem 3.15 in [2] T (m_{g+1} − 1) = T (m_{g+1} − 2) = T (m_{g+1} − 3) = 3^{g+1}. But by definition we have that T (m_{g+1} −1) = U(m_{g+1} −1)+U(m_{g+1} −2)+U(m_{g+1} −3) = T (m_{g+1} − 2) = U(m_{g+1}−2)+U(m_{g+1}−3)+U(m_{g+1}−4). Hence it follows that U(m_{g+1}−1) = U(m_{g+1}− 4). Similarly we derive from T (m_{g+1} − 2) = T (m_{g+1} − 3) that U(m_{g+1} − 2) = U(m_{g+1} − 5). By Proposition 2.2 in [2] Δ_{2}U(t) = U(t + 2) − U(t) ∈ {0, 2} for any positive integer t. Thus U(m_{g+1} − 1) ≥ U(m_{g+1} − 3) ≥ U(m_{g+1} − 5) = U(m_{g+1} − 2) ≥ U(m_{g+1} − 4) = U(m_{g+1} − 1). So U(m_{g+1} − 1) = U(m_{g+1} − 2) = U(m_{g+1} − 3) = \frac{1}{3}T (m_{g+1} − 1) = 3^{g}. This completes the proof of the second part of the statement of the lemma.

It remains to prove that for n ∈ [m_{g}, m_{g+1} −1], 3^{g−1} ≤ U(n), U(n−1), U(n−2) ≤ 3^{g}. By the above argument we have U(m_{g} − 1) = U(m_{g} − 2) = U(m_{g} − 3) = (\frac{1}{3})T (m_{g} − 1) = 3^{g−1}. Since Δ_{2}U(t) = U(t + 2) − U(t) ∈ {0, 2} for any positive integer t it follows that each of the subsequences of U(n) defined on the sets {n ∈ gen(g) : n ≡ m_{g} (mod 2)} and {n ∈ gen(g) : n ≡ m_{g+1} (mod 2)} is monotone non-decreasing (since Δ_{2}U(n) ∈ {0, 2} for all n), and that each of these subsequences for generation g begins with at least 3^{g−1} and ends no higher than 3^{g}. This concludes the proof.

Now consider the recursion (1.1) with k = 3 and s = 1 (“shift parameter 1”), namely,

T_{1}(n) = T_{1}(n − 1 − T_{1}(n − 1)) + T_{1}(n − 2 − T_{1}(n − 2)) + T_{1}(n − 3 − T_{1}(n − 3)). (2.2)

Let U_{1}(n) = T_{1}(n − 1 − T_{1}(n − 1)), so T_{1}(n) = U_{1}(n) + U_{1}(n − 1) + U_{1}(n − 2). (Note that our notation suppresses the parameter k = 3.) Four initial conditions are required, and these are T_{1}(1) = T_{1}(2) = T_{1}(3) = T_{1}(4) = 1. For 2 ≤ g, we define the (g − 1)^{th} generation of the “shifted” sequence T_{1}(n) as the interval n ∈ [m_{g−1} + g, m_{g} + g]. For brevity we sometimes refer to this interval as the “shifted” (g − 1)^{th} generation. The main result is the following:

Theorem 2.2. Let 2 ≤ g. For n ∈ [m_{g−1} + g, m_{g} + g], the shifted (g − 1)^{th} generation, the following two statements about the values of T_{1}(n) and U_{1}(n) hold:

(1) For n ∈ [m_{g−1} +g, m_{g} +g −4], 3^{g−1} < T_{1}(n) < 3^{g} and 3^{g−2} ≤ U_{1}(n), U_{1}(n−1), U_{1}(n− 2) ≤ 3^{g−1}. For n ∈ [m_{g}+g−3, m_{g}+g], T_{1}(n) = 3^{g} and U_{1}(n) = U_{1}(n−1) = U_{1}(n−2) = 3^{g−1}.

(2) For n ∈ [m_{g−1} + g, m_{g} + g − 1], T_{1}(n) = T_{0}(n − g). For n ∈ [m_{g} + g − 2, m_{g} + g], T_{1}(n) = T_{0}(n − g − 1).

Note that the second part of (2) follows from (1); we include it for convenience as we’ll use it directly below. From (1) it follows that the sequence T_{1}(n) hits powers of 3 exactly 4 times at the end of each generation (recall that the sequence T_{0}(n) hits powers of 3 exactly 3 times at the end of each generation). From (2) we have that otherwise the sequences are the same, since for r ∈ [m_{g−1}, m_{g} − 1], T_{0}(r) = T_{1}(r + g) (since if r ∈ [m_{g−1}, m_{g} − 1], then r + g ∈ [m_{g−1} + g, m_{g} + g − 1]. Thus we have that the sequences are identical except for the frequency of the occurrences of the powers of 3. Compare Tables 2 and 3 for an illustration of this.

Proof. Here we require a nested induction, on both g and n. We begin with the induction on g, the “outer induction”. For g = 2 we check each of the statements numerically for the shifted first generation. We begin with (1). Here n ∈ [m_{g−1} + g, m_{g} + g − 4] = [(\frac{1}{2})3^{g} + \frac{5}{2} + g, (\frac{1}{2})3^{g+1}+ \frac{5}{2} +g−4] = [9, 14]. For n in this interval it follows from the definition of U_{1}(n) that each of U_{1}(n), U_{1}(n − 1), U_{1}(n − 2) are contained in the set {T_{1}(3), T_{1}(4), …, T_{1}(8)} = {1, 3} so the first part of (1) holds. Further, U_{1}(16) = U_{1}(15) = U_{1}(14) = T_{1}(8) = 3, so this completes the proof of (1). In a similar way we confirm that (2) holds. Thus the base case is done.

Suppose both (1) and (2) hold for the 1^{st}, 2^{nd}, …, (g−2)^{th} shifted generations with g ≥ 3. We complete the induction on g by proving that they both hold for the (g − 1)^{th} shifted generation, which is the interval n ∈ [m_{g−1} +g, m_{g} +g]. Once again we proceed by induction, this time on n; this is what we call the “inner induction”.

We begin by confirming that (1) and (2) hold for the initial value of this interval, namely n = m_{g−1} + g. Specifically, we need to confirm that for this value of n, T_{1}(n) ∈ (3^{g−1}, 3^{g}), U_{1}(n), U_{1}(n − 1), U_{1}(n − 2) ∈ [3^{g−2}, 3^{g−1}], and further T_{1}(n) = T_{0}(n − g).

Since n = m_{g−1}+g is the first term of the (g−1)^{th} shifted generation, n−1 = m_{g−1}+g−1 is the last term of the (g −2)^{th} shifted generation. But by the induction assumption on g, (1) holds for the (g−2)^{th} shifted generation. Thus, T_{1}(n−1) = 3^{g−1}, while U_{1}(n−1) = U_{1}(n−2) = U_{1}(n−3) = 3^{g−2}. Also, U_{1}(n) = T_{1}(n−1−T_{1}(n−1)) = T_{1}(m_{g−1} +g −1−3^{g−1}) = T_{1}(m_{g−2} + g−1). Note that m_{g−2}+g−1 is the first member of the (g−2)^{th} shifted generation (so it’s not among the last four terms of the generation). It follows by the induction assumption on g that U_{1}(n) = T_{1}(m_{g−2}+g−1) ∈ (3^{g−2}, 3^{g−1}). So T_{1}(n) = U_{1}(n)+U_{1}(n−1)+U_{1}(n−2) ∈ (3^{g−1}, 3^{g}) and U_{1}(n), U_{1}(n − 1), U_{1}(n − 2) ∈ [3^{g−2}, 3^{g−1}]. This confirms (1).

We prove (2) similarly. By the above argument U_{1}(n) = T_{1}(m_{g−2} + g − 1) so by the induction assumption on g for (2) for the (g − 2)^{th} shifted generation we have U_{1}(n) = T_{1}(m_{g−2}+g−1) = T_{0}(m_{g−2}). Since n = m_{g−1}+g, we have T_{0}(n−g−1) = T_{0}(m_{g−1}−1) = 3^{g−1} by Theorem 4.3 in [2], so U_{0}(n−g) = T_{0}(n−g−T_{0}(n−g−1)) = T_{0}(m_{g−1}−3^{g−1}) = T_{0}(m_{g−2}). Thus we get U_{1}(n) = T_{0}(m_{g−2}) = U_{0}(n − g). By Theorem 4.3 in [2] again, T_{0}(n − g − 2) = T_{0}(m_{g−1} − 2) = 3^{g−1} and T_{0}(n − g − 3) = T_{0}(m_{g−1} − 3) = 3^{g−1}, so direct substitution gives us U_{0}(n−g−1) = T_{0}(n−g−1−T_{0}(n−g−2)) = T_{0}(m_{g−1}−1−3^{g−1}) = T_{0}(m_{g−2}−1) = 3^{g−2}, and U_{0}(n−g−2) = T_{0}(n−g−2−T_{0}(n−g−3)) = T_{0}(m_{g−1}−2−3^{g−1}) = T_{0}(m_{g−2}−2) = 3^{g−2}. Recall that above we have shown that U_{1}(n−1) = U_{1}(n−2) = 3^{g−2}, thus U_{1}(n−1) = U_{0}(n−g−1) and U_{1}(n−2) = U_{0}(n−g−2). Combining this with U_{1}(n) = U_{0}(n−g), we have T_{1}(n) = T_{0}(n−g). This concludes the base case for the “inner induction”.

For n in the (g − 1)^{th} shifted generation with n > m_{g−1} + g, we suppose the theorem is true for any number in this generation smaller than n, i.e. we suppose for any i ∈ [m_{g−1} + g, n − 1] = I(g; n − 1), the following two statements hold:

(1) For i ∈ [m_{g−1} + g, m_{g} + g − 4] ∩ I(g; n − 1), 3^{g−1} < T_{1}(i) < 3^{g} and 3^{g−2} ≤ U_{1}(i), U_{1}(i − 1), U_{1}(i − 2) ≤ 3^{g−1}. For i ∈ [m_{g} + g − 3, m_{g} + g] ∩ I(g; n − 1), T_{1}(i) = 3^{g} and U_{1}(i) = U_{1}(i − 1) = U_{1}(i − 2) = 3^{g−1}.

(2) For i ∈ [m_{g−1} + g, m_{g} + g − 1] ∩ I(g; n − 1), T_{1}(i) = T_{0}(i − g).

We need to show the theorem is true for i = n. This time we begin with (2). It’s sufficient to show U_{1}(n) = U_{0}(n−g), U_{1}(n−1) = U_{0}(n−g−1), U_{1}(n−2) = U_{0}(n−g−2), from which we conclude that T_{1}(n) = T_{0}(n−g) by definition. From [2] we have a thorough understanding of the values of T_{0}, so we deal with U_{0} first, working backwards. Since n ∈ [m_{g−1}+g, m_{g} +g−1], then n−g ∈ [m_{g−1}, m_{g} −1], which is the (g−1)^{th} generation (non-shifted). Thus by Theorem 3.15 in [2] and Lemma 2.1 above we have 3^{g−1} < T_{0}(n−g) ≤ 3^{g} and 3^{g−2} ≤ U_{0}(n−g), U_{0}(n− g − 1), U_{0}(n − g − 2) ≤ 3^{g−1}. Note that U_{0}(n − g) = T_{0}(n − g − T_{0}(n − g − 1)) ∈ [3^{g−2}, 3^{g−1}], by Theorem 3.15 in [2] again, and n − g − T_{0}(n − g − 1) ∈ [m_{g−2} − 3, m_{g−1} − 1]. Hence n−g−T_{0}(n−g−1)+g−1 ∈ [m_{g−2}+g−4, m_{g−1}+g−2]. For g ≥ 4 this latter interval is in the union of the (g − 2)^{th} shifted generation and the (g − 3)^{th} shifted generation, so (2) holds for this interval by the induction assumption on g. For g = 3, [m_{g−2}+g−4, m_{g−1}+g−2] = [6, 17], which equals the union of the intervals [6, 8] and [9, 17]. Further, [9, 17] is contained in the first generation where (2) holds by induction. So we need only check the values 6,7 and 8. By Tables 2 and 3 we confirm that T_{1}(6) = T_{0}(4), T_{1}(7) = T_{0}(5), T_{1}(8) = T_{0}(6). Thus T_{0}(n − g − T_{0}(n − g − 1)) = T_{1}(n − g − T_{0}(n − g − 1) + g − 1). And by the induction assumption on n, (2) holds for i = n − 1, so T_{1}(n − 1) = T_{0}(n − g − 1). In summary, we have U_{0}(n − g) = T_{0}(n − g − T_{0}(n − g − 1)) = T_{1}(n − g − T_{0}(n − g − 1) + g − 1) = T_{1}(n − g − T_{1}(n − 1)+g−1) = U_{1}(n). Similarly, U_{0}(n−g−1) = T_{0}(n−g−1−T_{0}(n−g−2)) ∈ [3^{g−2}, 3^{g−1}] yields n−g−1−T_{0}(n−g−2) ∈ [m_{g−2}−3, m_{g−1}−1] by the same reason above, while the same holds for T_{0}(n−g−1−T_{0}(n−g−2)) = T_{1}(n−g−1−T_{0}(n−g−2)+g−1) and T_{1}(n−2) = T_{0}(n−g−2). Direct substitution gives U_{0}(n − g − 1) = T_{1}(n − g − 1 − T_{1}(n − 2) + g − 1) = U_{1}(n − 1). Further by the same reasoning, we have U_{0}(n − g − 2) = U_{1}(n − 2). Combining the three equations above gives T_{1}(n) = T_{0}(n − g), which completes the proof of (2).

To prove (1) first notice that the value of T_{1}(n) is just the value of T_{0}(n − g), and the values of U_{1}(n), U_{1}(n − 1), U_{1}(n − 2) are just the values of U_{0}(n − g), U_{0}(n − g − 1) and U_{0}(n − g − 2), where n − g ∈ [m_{g−1}, m_{g} − 1] is in the (g − 1)^{th} generation (nonshifted). By [2] and Lemma 2.1 we know exactly the range of these values, so (1) follows immediately. Finally, the value of T_{1}(m_{g} + g) is readily computed as follows: by definition T_{1}(m_{g} + g) = U_{1}(m_{g} + g) + U_{1}(m_{g} + g − 1) + U_{1}(m_{g} + g − 2) = 3^{g}. By Theorem 4.3 in [2] again, T_{0}(m_{g} − 1) = T_{0}(m_{g} − 2) = T_{0}(m_{g} − 3) = 3^{g}, so by the induction assumption on g and direct substitution we have U_{1}(m_{g} + g) = T_{1}(m_{g} + g − 1 − T_{1}(m_{g} + g − 1)) = T_{1}(m_{g} + g − 1 − T_{0}(m_{g} +g −1−g)) = T_{1}(m_{g} +g −1−3^{g}) = T_{1}((\frac{1}{2})3^{g+1} + \frac{1}{2} +g −1−3^{g}) = T_{1}((\frac{1}{2})3^{g} +g − \frac{1}{2}) = T_{1}(m_{g−1}−1+g) = 3^{g−1}. Similarly we have U_{1}(m_{g} +g−1) = T_{1}(m_{g} +g−2−T_{1}(m_{g} +g−2)) = T_{1}(m_{g} + g − 2 − T_{0}(m_{g} + g − 2 − g)) = T_{1}(m_{g} + g − 2 − 3^{g}) = T_{1}(m_{g−1} − 2 + g) = 3^{g−1} and U_{1}(m_{g} + g − 2) = T_{1}(m_{g} + g − 3 − T_{1}(m_{g} + g − 3)) = T_{1}(m_{g} + g − 3 − T_{0}(m_{g} + g − 3 − g)) = T_{1}(m_{g} + g − 3 − 3^{g}) = T_{1}(m_{g−1} − 3 + g) = 3^{g−1}. Summing these we obtain T_{1}(m_{g} + g) = 3^{g} = T_{0}(m_{g} − 1). Thus both (1) and (2) are confirmed for T_{1}(m_{g} + g). This completes the “inner induction” on n, so the theorem is true for n ∈ [m_{g−1} + g, m_{g} + g], the (g − 1)^{th} shifted generation, as required. This completes the outer induction on g and hence the proof of Theorem 2.2.

3 The behavior of T_{s,3}(n) for s ≥ 1

Now we consider the behavior of the sequence generated by (1.1) with k = 3, shift parameter s ≥ 1 and initial conditions T_{s}(1) = T_{s}(2) = T_{s}(3) = ... = T_{s}(s + 3) = 1. Let U_{s}(n) = T_{s}(n − s − T_{s}(n − 1)), so T_{s}(n) = U_{s}(n) + U_{s}(n − 1) + U_{s}(n − 2). (Note that here our notation omits the subscript k = 3). Our goal is to generalize Theorem 2.2 as follows:

Theorem 3.1. Let 2 ≤ g. For n ∈ [m_{g−1} + gs, m_{g} + (g + 1)s − 1], the shifted (g − 1)^{th} generation, the following two statements hold:

(1) For n ∈ [m_{g−1} + gs, m_{g} + gs − 4], 3^{g−1} < T_{s}(n) < 3^{g} and 3^{g−2} ≤ U_{s}(n), U_{s}(n − 1), U_{s}(n − 2) ≤ 3^{g−1}. For n ∈ [m_{g} + gs − 3, m_{g} + (g + 1)s − 1], T_{s}(n) = 3^{g} and U_{s}(n) = U_{s}(n − 1) = U_{s}(n − 2) = 3^{g−1}. We say (1) holds for the pair (s, g − 1).

(2) For n ∈ [m_{g−1} +gs, m_{g} +(g+1)s−2], T_{s}(n) = T_{s−1}(n−g). For n ∈ [m_{g} +gs−2, m_{g} + (g + 1)s − 1], T_{s}(n) = T_{s−1}(n − g − 1). For r ∈ [m_{g−1} + g(s − 1), m_{g} + (g + 1)(s − 1) − 1], T_{s−1}(r) = T_{s}(r + g). We say (2) holds for the triple (s − 1, s, g − 1).

Proof. Observe that for s = 1 we know that (1) holds for (1, g) for all g by Theorem 2.2, as does (2) for the triple (s − 1, s, g) = (0, 1, g) for all g.

For an arbitrary positive integer s greater than 1, we proceed by induction on s. By this we mean that for all g we assume that (1) holds for all the s pairs (0, g), (1, g), …, (s − 1, g) and that (2) holds for the s−1 triples (0, 1, g), (1, 2, g), …, (s−2, s−1, g). Our immediately preceding observation establishes the base case for the induction argument.

We need to show that (1) holds for the pair (s, g) and (2) holds for the triple (s − 1, s, g). To do this we imitate the proof of Theorem 2.2, once again applying a double induction on both g and n (so overall a triple induction!). We begin with the so called “outer induction” on g.

We first establish the base case for g = 2. From the initial conditions T_{s}(1) = T_{s}(2) = T_{s}(3) = ... = T_{s}(s + 3) = 1 we have, by direct substitution, T_{s}(s + 4) = T_{s}(s + 5) = ... = T_{s}(2s + 6) = 3. Further direct computation yields that for n ∈ [m_{g−1} + gs, m_{g} + gs − 4] = [7 + 2s, 12 + 2s] we have T_{s}(n) ∈ (3, 9) and U_{s}(n), U_{s}(n − 1), U_{s}(n − 2) ∈ [1, 3]. And similar computation shows that for n ∈ [m_{g} +gs−3, m_{g} +(g +1)s−1] = [13+2s, 15+3s], T_{s}(n) = 9 and U_{s}(n) = U_{s}(n − 1) = U_{s}(n − 2) = 3. This confirms (1).

In a similar way we compute the values of T_{s−1}(n−g). Combining these with the values of T_{s}(n), we find that (2) is immediate. This concludes the base case for the “outer induction”, that is, (1) holds for the pair (s, 1) and (2) holds for the triple (s − 1, s, 1).

The induction assumption is that (1) holds for the pairs (s, 1), (s, 2), …, (s, g − 2) and (2) holds for the triples (s − 1, s, 1), (s − 1, s, 2), …, (s − 1, s, g − 2). We want to show that (1) holds for the pair (s, g − 1) and (2) holds for the triple (s − 1, s, g − 1).

We proceed by an “inner induction” on n within the (g −1)^{th} shifted generation, which is the interval n ∈ [m_{g−1} +gs, m_{g} +(g +1)s−1]. First we check the initial value n = m_{g−1} +gs. Specifically, we confirm that for this value of n, T_{s}(n) ∈ (3^{g−1}, 3^{g}), U_{s}(n), U_{s}(n−1), U_{s}(n−2) ∈ [3^{g−2}, 3^{g−1}], and further T_{s}(n) = T_{s−1}(n − g).

Since n = m_{g−1}+gs is the first term of the (g−1)^{th} shifted generation, n−1 = m_{g−1}+gs−1 is the last term of the (g − 2)^{th} shifted generation. By the induction assumption on g, (1) holds for (s, g − 2). Thus T_{s}(n − 1) = 3^{g−1}, while U_{s}(n − 1) = U_{s}(n − 2) = U_{s}(n − 3) = 3^{g−2}. So U_{s}(n) = T_{s}(n − s − T_{s}(n − 1)) = T_{s}(m_{g−1} + gs − s − 3^{g−1}) = T_{s}(m_{g−2} + (g − 1)s). Note that m_{g−2} + (g − 1)s is the first member of the (g − 2)^{th} shifted generation. Since there are more than s + 3 terms in the generation and only the last s + 3 terms are powers of 3 it follows by the induction assumption on g that U_{s}(n) = T_{s}(m_{g−2} +(g −1)s) ∈ (3^{g−2}, 3^{g−1}). So T_{s}(n) = U_{s}(n)+U_{s}(n−1)+U_{s}(n−2) ∈ (3^{g−1}, 3^{g}) and U_{s}(n), U_{s}(n−1), U_{s}(n−2) ∈ [3^{g−2}, 3^{g−1}]. This confirms (1).

We prove (2) similarly. By the above argument U_{s}(n) = T_{s}(m_{g−2} + (g − 1)s), so by the induction assumption on g that (2) holds for (s − 1, s, g − 2) we have U_{s}(n) = T_{s}(m_{g−2} + (g − 1)s) = T_{s−1}(m_{g−2} + (g − 1)(s − 1)). Since n = m_{g−1} + gs, we have T_{s−1}(n − g − 1) = T_{s−1}(m_{g−1} + g(s − 1) − 1) = 3^{g−1} by the induction assumption on s that (1) holds for (s−1, g −2). So U_{s−1}(n−g) = T_{s−1}(n−g −s−T_{s−1}(n−g −1)) = T_{s−1}(m_{g−1} +g(s−1)−(s− 1)−T_{s−1}(m_{g−1}+gs−g−1)) = T_{s−1}(m_{g−1}−3^{g−1}+(g−1)(s−1)) = T_{s−1}(m_{g−2}+(g−1)(s−1)). Thus we get U_{s}(n) = T_{s−1}(m_{g−2} + (g − 1)(s − 1)) = U_{s−1}(n − g).

Note that n−g−1 = m_{g−1} +g(s−1)−1 is the last term of the (g−2)^{th} shifted generation for the parameter (s−1). Hence by the induction assumption on s, U_{s−1}(n−g−1) = U_{s−1}(n− g−2) = U_{s−1}(n−g−3) = 3^{g−2}. Recall we have shown above that U_{s}(n−1) = U_{s}(n−2) = 3^{g−2}. Thus U_{s}(n − 1) = U_{s−1}(n − g − 1) and U_{s}(n − 2) = U_{s−1}(n − g − 2). Combining this with U_{s}(n) = U_{s−1}(n − g), we have T_{s}(n) = T_{s−1}(n − g). This concludes the base case for the “inner induction”.

For general n in the shifted (g − 1)^{th} generation, with n > m_{g−1} + gs, we suppose the theorem is true for any number in this generation smaller than n, i.e. we suppose for any i ∈ [m_{g−1} + gs, n − 1] = I(s, g; n − 1), the following two statements hold:

(1) For i ∈ [m_{g−1} + gs, m_{g} + gs − 4] ∩ I(s, g; n − 1), 3^{g−1} < T_{s}(i) < 3^{g} and 3^{g−2} ≤ U_{s}(i), U_{s}(i − 1), U_{s}(i − 2) ≤ 3^{g−1}. For i ∈ [m_{g} + gs − 3, m_{g} + (g + 1)s − 1] ∩ I(s, g; n − 1), T_{s}(i) = 3^{g} and U_{s}(i) = U_{s}(i − 1) = U_{s}(i − 2) = 3^{g−1}. We say (1) holds for i.

(2) For i ∈ [m_{g−1} + gs, m_{g} + (g + 1)s − 2] ∩ I(s, g; n − 1), T_{s}(i) = T_{s−1}(i − g). We say (2) holds for i.

We show now that both (1) and (2) are true for i = n. This time we begin with (2). Since T_{s}(n) = U_{s}(n) + U_{s}(n − 1) + U_{s}(n − 2) it’s sufficient to show U_{s}(n) = U_{s−1}(n − g), U_{s}(n − 1) = U_{s−1}(n − g − 1), U_{s}(n − 2) = U_{s−1}(n − g − 2), from which we conclude that T_{s}(n) = T_{s−1}(n − g). By the induction assumption on s we have that (1) holds for (s − 1, 1), (s − 1, 2), …, (s − 1, g − 1). Thus we have a thorough understanding of the values of T_{s−1}, so we deal with U_{s−1} first, working backwards.

As in the statement of (2) above, first we consider n ∈ [m_{g−1} + gs, m_{g} + (g + 1)s − 2]. Then n−g ∈ [m_{g−1} +g(s−1), m_{g} +(g+1)(s−1)−1], which is the (g−1)^{th} shifted generation for parameter s − 1. Therefore by (1) for (s − 1, g − 1) we have 3^{g−1} < T_{s−1}(n − g) ≤ 3^{g} and 3^{g−2} ≤ U_{s−1}(n − g), U_{s−1}(n − g − 1), U_{s−1}(n − g − 2) ≤ 3^{g−1}. By the definition of U we have U_{s−1}(n − g) = T_{s−1}(n − g − (s − 1) − T_{s−1}(n − g − 1)). But 3^{g−2} ≤ U_{s−1}(n − g) ≤ 3^{g−1} so T_{s−1}(n − g − (s − 1) − T_{s−1}(n − g − 1)) ∈ [3^{g−2}, 3^{g−1}.

Further, by the induction assumption on (1) for (s − 1, g − 3) and (s − 1, g − 2) we have that n−g−(s−1)−T_{s−1}(n−g−1) ∈ [m_{g−2} +(g−2)(s−1)−3, m_{g−1} +g(s−1)−1]. But note that this interval consists of the last three members of the (g − 3)^{th} shifted generation for parameter s − 1 together with all of the (g − 2)^{th} shifted generation for parameter s − 1. By the induction assumption on g it follows that (2) holds for (s−1, s, g −3) and (s−1, s, g −2) so it holds on this interval. Now let r = n − g − (s − 1) − T_{s−1}(n − g − 1) which is in this interval. Then we have T_{s−1}(r) = T_{s}(r + g − 1).

But by the induction assumption on the parameter n that (2) holds for n − 1 we have T_{s}(n−1) = T_{s−1}(n−g −1). Thus T_{s}(r+g −1) = T_{s}(n−g −(s−1)−T_{s−1}(n−g −1)+g −1) = T_{s}(n−g −(s−1)−T_{s}(n−1)+g −1). The last term is just U_{s}(n). But T_{s−1}(r) = U_{s−1}(n−g). Thus U_{s−1}(n − g) = U_{s}(n).

Similarly, U_{s−1}(n−g −1) = T_{s−1}(n−g −1−(s−1)−T_{s−1}(n−g −2)) ∈ [3^{g−2}, 3^{g−1}] yields n − g − 1 − (s − 1) − T_{s−1}(n − g − 2) ∈ [m_{g−2} + (g − 2)(s − 1) − 3, m_{g−1} + g(s − 1) − 1] by the same reason as above, while the same holds for T_{s−1}(n − g − 1 − (s − 1) − T_{s−1}(n − g − 2)) = T_{s}(n − g − 1 − (s − 1) − T_{s−1}(n − g − 2) + g − 1) and T_{s}(n − 2) = T_{s−1}(n − g − 2). Direct substitution gives U_{s−1}(n − g − 1) = T_{s}(n − 1 − s − T_{s}(n − 2)) = U_{s}(n − 1). Further, by the same reasoning, we have U_{s−1}(n − g − 2) = U_{s}(n − 2). Combining the three equations above we get T_{s}(n) = T_{s−1}(n − g).

This proves the initial claim in (2). We conclude the proof of (2) below by directly computing the value of T_{s}(m_{g} + (g + 1)s − 1), which is the value of T at the last term in the shifted (g − 1)^{th} generation for parameter s.

To prove (1) first notice that the value of T_{s}(n) is just the value of T_{s−1}(n − g), and the values of U_{s}(n), U_{s}(n − 1), U_{s}(n − 2) are just the values of U_{s−1}(n − g), U_{s−1}(n − g − 1) and U_{s−1}(n − g − 2), where n − g ∈ [m_{g−1} + g(s − 1) + 1, m_{g} + (g + 1)(s − 1) − 1] is in the (g − 1)^{th} shifted generation for parameter s − 1. By the induction assumption on s we know exactly the range of these values, so (1) follows immediately.

Finally, we compute the value of T_{s}(m_{g} + (g + 1)s − 1) as follows: by definition T_{s}(m_{g} + (g +1)s−1) = U_{s}(m_{g} +(g +1)s−1)+U_{s}(m_{g} +(g +1)s−2)+U_{s}(m_{g} +(g +1)s−3) = 3^{g}. By the induction assumption on s, T_{s−1}(m_{g} +(g +1)(s−1)−1) = T_{s−1}(m_{g} +(g +1)(s−1)−2) = T_{s−1}(m_{g}+(g+1)(s−1)−3) = 3^{g}. So by the induction assumption on g and direct substitution we have U_{s}(m_{g} +(g+1)s−1) = T_{s}(m_{g} +(g+1)s−1−s−T_{s}(m_{g} +(g+1)s−2)) = T_{s}(m_{g} +(g+ 1)s−1−s−T_{s−1}(m_{g} +(g +1)(s−1)−1)) = T_{s}(m_{g} +gs−1−3^{g}) = T_{s}(m_{g−1} −1+gs) = 3^{g−1}. Recall above we’ve shown that U_{s}(m_{g} + (g + 1)s − 2) = U_{s}(m_{g} + (g + 1)s − 3) = 3^{g−1} since m_{g} +(g+1)s−2 is in the (g−1)^{th} shifted generation and is not the last term. Summing these we obtain T_{s}(m_{g} +(g+1)s−1) = 3^{g} = T_{s−1}(m_{g} +(g+1)(s−1)−1) = T_{s−1}(m_{g} +(g+1)s−1− (g+1)). Thus both (1) and (2) are confirmed for T_{s}(m_{g} +(g+1)s−1). This finishes the proof of both (1)and (2) for i = n. Thus the theorem is true for n ∈ [m_{g−1} + gs, m_{g} + (g + 1)s − 1], the (g − 1)^{th} shifted generation, thereby completing the “inner induction” on n.

This completes the “outer induction” on g and hence the induction on s.

4 The behavior of T_{s,k}(n) for s ≥ 1 and odd k

The arguments in Section 2 and Section 3 for the case k = 3 rely on several key results from [2], analogues of which hold for any odd k. It follows that we can generalize all of the preceding, in particular Lemma 2.1 and Theorem 3.1, in a natural way. Because the proofs would be entirely analogous to (but even more tedious than) the ones given above we limit ourselves to a statement of these extensions.

Consider the recursion (1.1) with s ≥ 0, odd k ≥ 3, and the initial conditions T_{s,k}(n) = 1 for 1 ≤ n ≤ s + k. Define U_{s,k}(n) = T_{s,k}(n − s − T_{s,k}(n − 1)). Once again, as in Definition 5.7 in [2], for any g > 0 call the interval (of the domain of the sequence) [m_{g}, m_{g+1} − 1] the g^{th} generation of the sequence T_{s,k}(n), written as gen(g), where m_{g} = \frac{1}{k−1}(k^{g+1} + k^{2} − k − 1).

Lemma 4.1. Let 2 ≤ g, and suppose that n is in the (g − 1)^{th} generation. Then k^{g−2} ≤ U_{s,k}(n), U_{s,k}(n − 1), …, U_{s,k}(n − k + 1) ≤ k^{g−1}. Moreover, if n is the last term of the generation, then U_{s,k}(n) = U_{s,k}(n − 1) = ⋯ = U_{s,k}(n − k + 1) = k^{g−1}.

Theorem 4.2. Let s ≥ 1 and 2 ≤ g. For n ∈ [m_{g−1} + gs, m_{g} + (g + 1)s − 1], the shifted (g − 1)^{th} generation, the following two statements hold:

(1) If n is one of the last k + s terms of the generation, then T_{s,k}(n) = k^{g} and U_{s,k}(n) = U_{s,k}(n − 1) = ⋯ = U_{s,k}(n − k + 1) = k^{g−1}. If n is any other member of the generation, then k^{g−1} < T_{s,k}(n) < k^{g} and k^{g−2} ≤ U_{s,k}(n), U_{s,k}(n − 1), …, U_{s,k}(n − k + 1) ≤ k^{g−1}.

(2) If n is the last term of the generation, T_{s,k}(n) = T_{s−1,k}(n − g − 1). If n is any other member of the generation, then T_{s,k}(n) = T_{s−1,k}(n − g).

Table 5: First 180 terms of T_{0,4}(n) with initial values (1, 1, 1, 1)

n  n  n
1  2  3  1  2  3  1  2  3
T (n + 0)  1  1  1  T (n + 60)  46  46  49  T (n + 120)  94  91  91
T (n + 3)  1  4  4  T (n + 63)  49  46  52  T (n + 123)  94  94  94
T (n + 6)  4  4  7  T (n + 66)  52  49  55  T (n + 126)  97  97  94
T (n + 9)  7  7  10  T (n + 69)  52  52  58  T (n + 129)  100  100  97
T (n + 12)  7  10  13  T (n + 72)  55  55  58  T (n + 132)  103  100  100
T (n + 15)  10  13  13  T (n + 75)  55  58  61  T (n + 135)  106  103  103
T (n + 18)  13  16  16  T (n + 78)  58  61  61  T (n + 138)  106  103  106
T (n + 21)  16  16  16  T (n + 81)  61  64  64  T (n + 141)  109  106  109
T (n + 24)  19  19  19  T (n + 84)  64  64  64  T (n + 144)  109  109  112
T (n + 27)  22  19  22  T (n + 87)  64  67  67  T (n + 147)  112  112  112
T (n + 30)  25  22  25  T (n + 90)  67  70  67  T (n + 150)  112  115  115
T (n + 33)  25  25  28  T (n + 93)  70  73  70  T (n + 153)  115  118  115
T (n + 36)  28  28  28  T (n + 96)  73  73  73  T (n + 156)  118  121  118
T (n + 39)  31  31  31  T (n + 99)  76  76  76  T (n + 159)  121  121  121
T (n + 42)  34  31  34  T (n + 102)  76  79  79  T (n + 162)  124  124  124
T (n + 45)  37  34  37  T (n + 105)  79  82  79  T (n + 165)  124  127  127
T (n + 48)  37  34  40  T (n + 108)  82  85  82  T (n + 168)  127  130  127
T (n + 51)  40  37  43  T (n + 111)  85  85  82  T (n + 171)  130  133  130
T (n + 54)  40  40  46  T (n + 114)  88  88  85  T (n + 174)  133  133  130
T (n + 57)  43  43  46  T (n + 117)  91  88  88  T (n + 177)  136  136  133

Table 6: First 180 terms of T_{1,4}(n) with initial values (1, 1, 1, 1, 1)

n  n  n
1  2  3  1  2  3  1  2  3
T (n + 0)  1  1  1  T (n + 60)  43  43  46  T (n + 120)  85  91  88
T (n + 3)  1  1  4  T (n + 63)  46  46  49  T (n + 123)  88  94  91
T (n + 6)  4  4  4  T (n + 66)  49  46  52  T (n + 126)  91  94  94
T (n + 9)  4  7  7  T (n + 69)  52  49  55  T (n + 129)  94  97  97
T (n + 12)  7  10  7  T (n + 72)  52  52  58  T (n + 132)  94  100  100
T (n + 15)  10  13  10  T (n + 75)  55  55  58  T (n + 135)  97  103  100
T (n + 18)  13  13  13  T (n + 78)  55  58  61  T (n + 138)  100  106  103
T (n + 21)  16  16  16  T (n + 81)  58  61  61  T (n + 141)  103  106  103
T (n + 24)  16  16  16  T (n + 84)  61  64  64  T (n + 144)  106  109  106
T (n + 27)  19  19  19  T (n + 87)  64  64  64  T (n + 147)  109  109  109
T (n + 30)  22  19  22  T (n + 90)  64  64  67  T (n + 150)  112  112  112
T (n + 33)  25  22  25  T (n + 93)  67  67  70  T (n + 153)  112  112  115
T (n + 36)  25  25  28  T (n + 96)  67  70  73  T (n + 156)  115  115  118
T (n + 39)  28  28  28  T (n + 99)  70  73  73  T (n + 159)  115  118  121
T (n + 42)  31  31  31  T (n + 102)  73  76  76  T (n + 162)  118  121  121
T (n + 45)  34  31  34  T (n + 105)  76  76  79  T (n + 165)  121  124  124
T (n + 48)  37  34  37  T (n + 108)  79  79  82  T (n + 168)  124  124  127
T (n + 51)  37  34  40  T (n + 111)  79  82  85  T (n + 171)  127  127  130
T (n + 54)  40  37  43  T (n + 114)  82  85  85  T (n + 174)  127  130  133
T (n + 57)  40  40  46  T (n + 117)  82  88  88  T (n + 177)  130  133  133

Table 7: First 180 terms of T_{2,4}(n) with initial values (1, 1, 1, 1, 1, 1)

n  n  n
1  2  3  1  2  3  1  2  3
T (n + 0)  1  1  1  T (n + 60)  40  40  46  T (n + 120)  85  82  88
T (n + 3)  1  1  1  T (n + 63)  43  43  46  T (n + 123)  88  85  91
T (n + 6)  4  4  4  T (n + 66)  46  46  49  T (n + 126)  88  88  94
T (n + 9)  4  4  4  T (n + 69)  49  46  52  T (n + 129)  91  91  94
T (n + 12)  7  7  7  T (n + 72)  52  49  55  T (n + 132)  94  94  97
T (n + 15)  10  7  10  T (n + 75)  52  52  58  T (n + 135)  97  94  100
T (n + 18)  13  10  13  T (n + 78)  55  55  58  T (n + 138)  100  97  103
T (n + 21)  13  13  16  T (n + 81)  55  58  61  T (n + 141)  100  100  106
T (n + 24)  16  16  16  T (n + 84)  58  61  61  T (n + 144)  103  103  106
T (n + 27)  16  16  16  T (n + 87)  61  64  64  T (n + 147)  103  106  109
T (n + 30)  19  19  19  T (n + 90)  64  64  64  T (n + 150)  106  109  109
T (n + 33)  22  19  22  T (n + 93)  64  64  64  T (n + 153)  109  112  112
T (n + 36)  25  22  25  T (n + 96)  67  67  67  T (n + 156)  112  112  112
T (n + 39)  25  25  28  T (n + 99)  70  67  70  T (n + 159)  115  115  115
T (n + 42)  28  28  28  T (n + 102)  73  70  73  T (n + 162)  118  115  118
T (n + 45)  31  31  31  T (n + 105)  73  73  76  T (n + 165)  121  118  121
T (n + 48)  34  31  34  T (n + 108)  76  76  76  T (n + 168)  121  121  124
T (n + 51)  37  34  37  T (n + 111)  79  79  79  T (n + 171)  124  124  124
T (n + 54)  37  34  40  T (n + 114)  82  79  82  T (n + 174)  127  127  127
T (n + 57)  40  37  43  T (n + 117)  85  82  85  T (n + 177)  130  127  130

5 Conjectures for even k

For even k the effect of the shift parameter s on the behavior of the sequences generated by (1.1) with the initial conditions T_{s,k}(n) = 1 for 1 ≤ n ≤ s + k appears to be quite similar. We conjecture that the sequences T_{s,k}(n) and T_{0,k}(n) are essentially the same, with the only differences in these sequences occurring in the frequencies with which the powers of k occur. In particular, in the sequence T_{s,k}(n) we conjecture that each value k^{r} occurs precisely s + k + (r − 1) times. See Tables 5, 6, and 7 for an example of this for k = 4 and s = 0, 1 and 2.

Observe that if the conjectures relating to even k in [2] hold then it should be possible to prove our present conjectures by following an approach analogous to the one adopted above.

6 Acknowledgements

The authors are grateful to Wendy Wu for her substantial assistance in the preparation of this manuscript.

References

[1] B. Balmohan, Z. Li and S. Tanny, A combinatorial interpretation for certain relatives of the Conolly sequence, J. Integer Sequences, 11 (2008), Article 08.2.1.

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

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

[4] B. Dalton and S. M. Tanny, Generational structure of meta-Fibonacci sequences, unpublished manuscript, 2005.

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

[6] B. Jackson and F. Ruskey, Meta-Fibonacci sequences, binary trees and extremal compact codes, Electronic J. Combinatorics 13 (2006), #R26.

[7] J. Higham and S. M. Tanny, More well-behaved meta-Fibonacci sequences, Congressus Numerantium 98 (1993), 3–17.

[8] J. Higham and S. M. Tanny, A tamely chaotic meta-Fibonacci sequence, Congressus Numerantium 99 (1994), 67–94.

[9] F. Ruskey, private communication (2007).

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

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

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

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11B99.

Keywords: Hofstadter, iterated recursion, meta-Fibonacci, Q sequence.

Received June 2 2008; revised version received August 15 2008. Published in Journal of Integer Sequences, August 17 2008.

Return to Journal of Integer Sequences home page.