A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions

Nathaniel D. Emerson Department of Mathematics California State University, Channel Islands One University Drive Camarillo, California 93012-8599 USA

              Nathaniel.Emerson@csuci.edu

Abstract

We define a family of meta-Fibonacci sequences. For each sequence in the family, the order of the of the defining recursion at the n^{th} stage is a variable r(n), and the n^{th} term is the sum of the previous r(n) terms. Given a sequence of real numbers that satisfies some conditions on growth, there is a meta-Fibonacci sequence in the family that grows at the same rate as the given sequence. In particular, the growth rate of these sequences can be exponential, polynomial, or logarithmic. However, the possible asymptotic limits of such a sequence are restricted to a class of exponential functions. We give upper and lower bounds for the terms of any such sequence, which depend only on r(n). The Narayana-Zidek-Capell sequence is a member of this family. We show that it converges asymptotically.

1 Introduction

We consider meta-Fibonacci sequences, by which we mean a sequence given by a Fibonaccitype recursion, where the recursion varies with the index. D. Hofstadter defined the first meta-Fibonacci sequence [10, p. 137]), which appears as \underline{A005185} in Sloane’s Encyclopedia of Integer Sequences. R. Guy posed some questions about this sequence, which remain open [9]. J. Conway [14], B. Conolly [4] and S. Tanny [17] proposed similar sequences; and good results about these sequences have been obtained. We define a new family of meta-Fibonacci sequences defined by variable order recursions. This family is considerably different from previously described families of meta-Fibonacci sequences [5, 12, 2] both in terms of its definition and behavior.

We define the family of meta-Fibonacci sequences that is the subject of this paper. The regular Fibonacci numbers are of course constructed by adding the previous two terms of the sequence: f_{n} = f_{n−1} + f_{n−2} (\underline{A000045}). Adding the previous three terms yields the Tribonacci numbers: t_{n} = t_{n−1} + t_{n−2} + t_{n−3} (\underline{A000073}). If we add the previous r terms, we obtain the r-generalized Fibonacci numbers (“r-bonacci numbers”): f_{r,n} = f_{r,n−1}+⋯+f_{r,n−r} (\underline{A092921}). In our family, we let r vary as a function of n. We call the resulting numbers variable-r meta-Fibonacci numbers. Let ℕ denote the non-negative integers and ℤ^{+} denote the positive integers.

Definition 1.1. Let r : ℕ → ℤ^{+} such that r(0) = 1, and r(n) ≤ n for all n ≥ 1. Define

b(n) = ∑_{k=1}^{r(n)} b(n − k), n ≥ 1,

with initial condition b(0) = 1. We call the sequence b(n) a variable-r meta-Fibonacci sequence, and say that r(n) generates b(n).

For brevity, we call such a b(n) an r(n)-bonacci sequence. Any such sequence is a nondecreasing sequence of positive integers. It is easy to show that any r(n)-bonacci sequence omits infinitely many positive integers. Additionally, distinct sequences, r(n), generate distinct sequences, b(n). Thus, we have defined an uncountable family of meta-Fibonacci sequences, in one-to-one correspondence with sublinear sequences of positive integers.

The focus of this paper is the growth of r(n)-bonacci sequences, b(n). We consider longterm growth. That is, the order of b(n) in terms of the Landau symbols O, Ω, and Θ. We also ask about short-term growth. That is, the value of the ratio of successive terms b(n)/b(n−1). The long-term growth is characterized by a wide range of possible behaviors. The short-term growth is highly irregular in general.

In this paper, we denote integer-valued sequences by Roman letters, and other sequences by Greek letters. Given a sequence of real numbers σ(n) that satisfies some mild conditions on growth, there is an r(n)-bonacci sequence b(n), which in the long term grows at approximately the same rate as σ(n). In particular, b(n) is Θ(σ(n)).

Theorem 1. Let σ(n) be a sequence of real numbers such that for all n sufficiently large, σ(n) is non-decreasing, σ(n) ≥ 1, and

σ(n + 1)/2 ≤ σ(n) ≤ 2^{n−1}.

Then there is a variable-r meta-Fibonacci sequence b(n) such that for all n sufficiently large,

σ(n)/2 < b(n) ≤ σ(n).

The conditions on σ(n) are mild enough that it is possible for σ(n) to be exponential, polynomial, or logarithmic (see Corollary 3.10). In contrast, the Fibonacci sequence (and the r-bonacci sequences) grow at an exponential rate. The growth rate of many previously described meta-Fibonacci sequences is linear when it is known [2, 4, 14, 17].

Consider the growth rate of the ordinary Fibonacci numbers. It is well known that the short-term growth rate converges to the Golden Section: (1 + \sqrt{5})/2. Hence, the long-term growth rate is exponential. Simiarly, the short-term growth rate of the r-bonacci numbers converges. Let α_{r} denote the growth rate of the r-bonacci numbers: f_{r,n}/f_{r,n−1} → α_{r} [15]. It is well-known that 1 < α_{r} < 2 for all r ≥ 2. For technical reasons, we define α_{1} = 1. The short-term growth rate of an r(n)-bonacci sequence does not necessarily converge (see Example 2.4). When it does converge, the only possible limits are 2 or α_{r} for some r ≥ 1. Moreover, it converges to α_{r} if and only if r(n) = r for all n sufficiently large. It follows that the class of sequences σ(n) such that b(n) ∼ σ(n) is restricted.

Theorem 2. Let σ(n) be a sequence of real numbers such that lim_{n→∞} σ(n)/σ(n − 1) exists and is non-zero. If

lim_{n→∞} \frac{b(n)}{σ(n)} = L

and 0 < L < ∞, then

lim_{n→∞} \frac{σ(n)}{σ(n − 1)} = 2, or lim_{n→∞} \frac{σ(n)}{σ(n − 1)} = α_{r}

for some r ≥ 1 and r(n) = r for all n sufficiently large.

Variable-r meta-Fibonacci numbers were originally discovered by the author while studying dynamical systems [7], specifically the dynamics of complex polynomials. One can consider closest return times, most intuitively, the iterates of a given point under some map that are closer to the point than any previous iterate. Certain generalized closest return times of polynomials are extended variable-r meta-Fibonacci numbers (see Section 5) [8]. This result generalizes the fact that there exist complex polynomials whose generalized closest return times are the ordinary Fibonacci numbers [1, Ex. 12.4].

We begin with a variety of examples of r(n)-bonacci sequences in Section 2. We then compare and contrast their behavior to the behavior of other families of meta-Fibonacci sequences.

We study the asymptotics of r(n)-bonacci sequences in Section 3. The growth rate of any r(n)-bonacci sequence is at most exponential. We give a condition for b(n) to grow exponentially. We prove Theorems 1 and 2.

We derive estimates for b(n) in terms of r(n) in Section 4. We give an iterative technique for finding upper and lower bounds for b(n)/b(n − 1). We compute upper and lower bounds for b(n) that do not depend on the previous terms of the sequence. We observe that the Narayana-Zidek-Capell numbers (\underline{A002083}) are r(n)-bonacci numbers. We show that they converge asymptotically to c2^{n−3} for some positive real number c.

In Section 5, we define a generalization of the r(n)-bonacci numbers by taking b(n) as a sequence defined on all integers. This generalization has applications in the field of polynomial dynamics.

2 Examples

Variable-r meta-Fibonacci sequences are considerably different from any previously described meta-Fibonacci sequence. We give several examples of several r(n)-bonacci sequences. Our goal is that the reader will develop some intuition for the sequences, particularly for how b(n) depends on r(n). We might hope to find a closed-form expression for a general b(n) or an expression that depends only on r(1), …, r(n). The examples of this section show that we can find a closed form in some cases, but in general it appears to be a difficult problem.

The main questions we pose in this paper are about the growth rate of b(n), in both the long term and the short term. The long-term growth is characterized by a wide range of possible behaviors. The short-term growth is highly irregular in general. In this section, we give specific examples of these phenomena. In Section 3, we give general results. Finally, we recall some other meta-Fibonacci sequences, most importantly other families of meta-Fibonacci sequences. We compare and contrast them with r(n)-bonacci sequences.

The proof of any claim made in the examples below has been left as an exercise.

First, we give the most elementary examples. If r(1) = 1 and r(n) = 2 for all n ≥ 2, then b(n) = f_{n+1}, where (f_{n}) is the usual Fibonacci sequence (\underline{A000045}). If r(n) = r ≥ 2 for all n sufficiently large, then up to re-indexing, the tail of b(n) is a generalized r-bonacci sequence (\underline{A092921}) for some initial conditions.

If r(n) = 1 for all n, then b(n) = 1 for all n. If r(n) = 1 for all n large, then b(n) is eventually constant. While this is a fairly trivial example, it demonstrates that the lower bound for growth in the r(n)-bonacci family is constant. That is, there are r(n)-bonacci sequences that are Θ(1). Conolly defined a meta-Fibonacci sequence by

K(n) = K(K(n − 1)) + K(K(n − 2)), n > 2,

K(1) = K(2) = 1 [4, p. 127]. He showed that K(n) = 2 for all n > 2. Thus, there is at least one previously described meta-Fibonacci sequence that is eventually constant. To the best of the author’s knowledge, this is the only previously described meta-Fibonacci sequence that does not grow at a polynomial rate. We can also generalize this example by taking r(n) = 1 for many n. This makes the short-term growth of b(n) small, and results in slow long-term growth (see Example 2.7).

At the other extreme, in the following example we take r(n) as large as allowed. The result is that b(n) is maximally large (see Proposition 3.4).

Example 2.1. Let r(n) = n for n ≥ 1, then b(n) = 2^{n−1} for n ≥ 1:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ r(n) & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ b(n) & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \end{matrix}

Doubling is a major theme in the behavior of b(n). The following example shows that b(n) can more than double for infinitely many n. Thus, the short-term growth can be rapid for infinitely many n. However, in order to make b(n)/b(n − 1) large, we must take r(n − 1) small. Therefore, the long-term growth is much slower than in the previous example.

Example 2.2. For n ≥ 1, let r(n) = n if n is even, and r(n) = 1 if n is odd:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ r(n) & 1 & 1 & 2 & 1 & 4 & 1 & 6 & 1 & 8 & 1 & 10 \\ b(n) & 1 & 1 & 2 & 2 & 6 & 6 & 18 & 18 & 54 & 54 & 162 \end{matrix}

It is straightforward to show that b(n) = 3b(n − 1) for n ≥ 4 and even.

The following example shows that b(n)/b(n − 1) → 2 occurs for non-constant sequences.

Example 2.3. For n ≥ 2, let r(n) = n for n even, and r(n) = n − 1 for n odd:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ r(n) & 1 & 1 & 2 & 2 & 4 & 4 & 6 & 6 & 8 & 8 \\ b(n) & 1 & 1 & 2 & 3 & 7 & 13 & 27 & 53 & 107 & 213 \end{matrix}

For n > 2, b(n) = 2b(n − 1) + 1 for n even, and b(n) = 2b(n − 1) − 1 for n odd. Hence, lim_{n→∞} b(n)/b(n − 1) = 2.

The following example shows that the short-term growth, the sequence (b(n)/b(n − 1)), need not converge.

Example 2.4. For n ≥ 2, let r(n) = 2 for n even, and r(n) = 3 for n odd:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ r(n) & 1 & 1 & 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 \\ b(n) & 1 & 1 & 2 & 4 & 6 & 12 & 18 & 36 & 54 & 108 \end{matrix}

It follows that b(n)/b(n − 1) = 2 for n > 2 and odd, and b(n)/b(n − 1) = 3/2 for n > 2 and even.

The following example shows how irregularly b(n) can grow in the short-term. We take a very irregular function for r(n), and generate a b(n) that grows irregularly.

Example 2.5. Let r(0) = 1, and r(n) = φ(n) for n > 0, where φ(n) is the Euler totient function (\underline{A000010}):

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ r(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 & 8 & 16 \\ b(n) & 1 & 1 & 2 & 3 & 7 & 10 & 24 & 44 & 90 & 168 & 350 & 652 & 1352 & 2656 & 5336 & 10628 & 21304 \end{matrix}

From the above examples, we can see that a closed form for b(n) can be found in some cases. However, finding a closed form in general appears to be a difficult problem. Even the more modest goal of finding an expression for b(n) that depends only on r(n) seems difficult. Although, we can find upper and lower bounds for b(n) that depend only on r(n) (see Theorem 4.6).

The next three sequences are examples of the long-term behavior of b(n). They show that through careful choice of r(n), we can make b(n) grow at a predetermined rate (see Theorem 1).

Example 2.6. Choose r(n) so that \sqrt{3}^{n}/2 < b(n) ≤ \sqrt{3}^{n} for all n ≥ 0:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ r(n) & 1 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 5 \\ b(n) & 1 & 1 & 2 & 4 & 8 & 8 & 16 & 32 & 64 & 64 & 128 & 256 & 512 & 1024 \end{matrix}

So b(n) is Θ(\sqrt{3}^{n}).

By taking r(n) = 1 frequently, we can have linear growth for b(n).

Example 2.7. For n ≥ 2, let r(n) = 2 if n = 2^{k} for some k ∈ ℕ, and r(n) = 1 otherwise:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ r(n) & 1 & 1 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 1 \\ b(n) & 1 & 1 & 2 & 2 & 4 & 4 & 4 & 4 & 8 & 8 \end{matrix}

It is easy to show that n/2 < b(n) ≤ n for n ≥ 1. That is, b(n) is Θ(n).

We can construct b(n) that grows logarithmically. No previously published meta-Fibonacci sequence grows logarithmically.

Example 2.8. For n ≥ 2, let r(n) = 2 if n = 2^{2^{k}} for some k ∈ ℕ, and r(n) = 1 otherwise:

\begin{matrix}n & 0 & 1 & 2 & 4 & 16 & 256 \\ r(n) & 1 & 1 & 2 & 2 & 2 & 2 \\ b(n) & 1 & 1 & 2 & 4 & 8 & 16 \end{matrix}

We have log_{2} n < b(n) ≤ 2 log_{2} n for n > 1. Hence, b(n) is Θ(log_{2} n).

Similarly, we can construct examples that are Θ(log_{2} log_{2} n), etc. Thus, b(n) can grow extremely slowly, even when it is not eventually constant.

We now recall some previously defined meta-Fibonacci sequences. We take Hofstadter’s Q-sequence (\underline{A005185}, [10, p. 137]) as a typical example. Let Q(1) = Q(2) = 1 and

Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), n > 2.

The first few terms are given below:

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ Q(n) & 1 & 1 & 2 & 3 & 3 & 4 & 5 & 5 & 6 & 6 & 6 & 8 & 8 & 8 & 10 & 9 & 10 & 11 & 11 & 12 \end{matrix}

The recursion for Q(n) is “self-referential.” The order of the recursion is fixed. The terms we add to obtain Q(n) are not necessarily the immediately previous terms. It may happen that for some n, we add terms that are early in the sequence and thus small, so Q(n) will be small. In contrast for an r(n)-bonacci sequence b(n), an “external variable,” r(n), controls the recursion. The order of the recursion is not generally fixed. We always add the immediately previous r(n) terms, so b(n) is always the sum of the greatest of the preceding terms. These differences result in Q(n) having much more complicated short-term behavior than b(n). The short-term behavior of Q(n) has been described as “chaotic” [10] (for instance Q(16) < Q(15)). In contrast, b(n) is non-decreasing.

Although the Hofstadter sequence is the oldest meta-Fibonacci sequence, some fundamental questions about it remain open. For example, is it well defined? Observe that it is well-defined if and only if Q(n) ≤ n for all n > 2. From this observation, we see that the fundamental question about Q(n) is really a question about its growth rate; if it is well defined, then its maximum possible growth rate is linear. In fact, it appears from numerical evidence that Q(n)/n → 1/2 [9]. Therefore, it seems that the long-term behavior of Q(n) is tame.

This observation illustrates a general property of self-referential sequences, including all previously published meta-Fibonacci sequences. We can compute an upper bound for the growth of any self-referential sequence from its recursion. For example, let s(n) be a sequence satisfying some self-referential recursion of the form

s(n) = s(n + c − s(n − d)) + (other terms),

for some c, d ∈ ℤ with initial condition(s) s(0), . . .. It follows that

s(n) ≤ n + c + d.

In particular, s(n) must be O(n).

In light of this property, it should not be surprising that most previously described meta-Fibonacci sequences grow linearly. For instance, the Tanny sequence (\underline{A006949}, [17]):

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

T (0) = T (1) = T (2). Our estimate gives T (n) ≤ n. In fact, it is known that T (n)/n → 1/2 [17, Prop. 2.7].

For an r(n)-bonacci sequence b(n), this argument is not useful. It implies we must have n − r(n) ≥ 0, which is built in to the definition of r(n). Therefore, we must use other methods to estimate the growth rate of b(n).

Since the r(n)-bonacci sequences are a family, we compare and contrast the family to known meta-Fibonacci families. The r-bonacci sequences can be regarded as a family of meta-Fibonacci sequences parameterized by r ≥ 2 (since r = 1 gives a constant sequence). It is a proper subfamily of the r(n)-bonacci family. This family is quite well understood. Every sequence in the family grows exponentially, and a closed form its terms is known [15].

J. Callaghan, J. Chew and S. Tanny studied a family of meta-Fibonacci sequences parameterized by a > 0, k > 1 [2]:

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 T_{a,k}(n) = 1 for 1 ≤ n ≤ a + k. This family generalizes the Tanny sequence (\underline{A006949}, [17]). Sub-families of this family have also been considered [11, 12]. For all a and all odd k, the growth rate of sequences in this family is linear [2, Cor. 5.14]:

lim_{n→∞} \frac{T_{a,k}(n)}{n} = \frac{k − 1}{k}.

In previously described meta-Fibonacci sequences, three orders of growth have been found: exponential, linear, and constant. Moreover, all of the sequences in each of the above meta-Fibonacci families have the same order of growth. We have given examples of all of these orders of growth and more in the r(n)-bonacci family. Part of the explanation for this difference is that both of the above families contain only countably many sequences. In contrast, there are uncountably many r(n)-bonacci sequences. When we define an r(n)- bonacci sequence, we get to make countably many choices for r(n). Each choice can be made in n(≥ 2) ways. These choices can be made recursively, so b(n) can be defined recursively to satisfy specified behavior on its growth. It follows that we can construct a wide variety of growth in the family (see Theorem 1).

R. Dawson, G. Gabor, R. Nowakowski and D. Wiens defined a family of meta-Fibonacci sequences by a random process [5]. A (p, q)-sequence (F_{n}) is defined as follows: Fix positive integers p and q and choose real numbers a_{1}, ⋯, a_{p}. Set F_{n} = a_{n} with probability one for n ≤ p. Let F_{n+1} = ∑_{k=1}^{q} F_{j_{k}} for n ≥ p, where the j_{k} are randomly chosen (with replacement) from (1, 2, ⋯, n) with the uniform distribution. Note that (p, q)-sequences are extremely general; any sequence defined by an order q linear recursion with positive integer coefficients can occur as a (p, q)-sequence. This includes all previously published meta-Fibonacci sequences. The authors did not address the question of the possible values of (F_{n}), instead they asked about its average value. The expected value of F_{n} is a polynomial in n of degree q − 1 [5, Thm. 1]. We propose the following interpretation of this result: a “typical” meta-Fibonacci sequence defined by a recursion of fixed order grows at a polynomial rate. Under this interpretation, there are r(n)-bonacci sequences that grow at the rate of a typical meta-Fibonacci sequence, but there are also r(n)-bonacci sequences that grow faster or slower.

In many ways, the family of (p, q)-sequences is the meta-Fibonacci family which is most similar to the r(n)-bonacci family: both families are uncountable; they properly contain the r-bonacci numbers; there are sequences in both families that grow at different rates (the Fibonacci sequence, the Tanny sequence, and an eventually constant sequence can all occur as (p, 2)-sequences). However, it is not always possible to make meaningful comparisons between the two families because (p, q)-sequences are random and r(n)-bonacci sequences are deterministic.

3 Asymptotic Growth

In this section, we examine the asymptotic growth of b(n). We show more precisely the variety of different growth rates that b(n) can have. Here, the r(n)-bonacci family is characterized by flexibility in its short-term growth. This flexibility leads to short-term oscillation, and the possible asymptotic limits are quite restricted. On the other hand, a wide range of possible long-term growth rates are possible.

After some preliminaries, we consider the short-term growth of b(n). The key question is about doubling: how does b(n)/b(n − 1) compare to 2? We give an answer based on r(n), which is the foundation of the rest of our results. We show that in the long term, no b(n) can more than double. We give a condition for b(n) to grow exponentially.

Given a sequence σ(n) that satisfies some mild conditions on growth, there is an r(n)- bonacci sequence that grows at the same rate as σ(n). This shows some of the broad range of possible growth rates that occur in the r(n)-bonacci family. In contrast, the asymptotic limits of b(n) are restricted. If b(n) ∼ σ(n), then σ(n) grows like an r-bonacci sequence or 2^{n}.

In this section, let b(n) be a variable-r meta-Fibonacci sequence generated by r(n). We state elementary conclusions about the limiting behavior of b(n).

Lemma 3.1. We have lim sup_{n→∞} r(n) = 1 if and only if b(n) is eventually constant.

Lemma 3.2. We have lim sup_{n→∞} r(n) > 1 if and only if lim_{n→∞} b(n) = ∞.

Thus, an r(n)-bonacci sequence converges if and only if it is eventually constant. We consider sequences that are not eventually constant.

We examine the short-term growth of b(n). For any given n, the larger r(n) is, the larger b(n) will be. However, it is Δr(n) = r(n) − r(n − 1) that has the greatest influence on the growth rate. The following lemma is our basic estimate; we give a condition for b(n) to double.

Lemma 3.3. If Δr(n) = 1 for some n ≥ 1, then b(n)/b(n − 1) = 2.

Proof. We have r(n) = r(n − 1) + 1. Hence,

b(n) = ∑_{k=1}^{r(n)} b(n − k)

= b(n − 1) + ∑_{k=2}^{r(n−1)+1} b(n − k)

= b(n − 1) + ∑_{j=1}^{r(n−1)} b(n − 1 − j)

= 2b(n − 1).

We give a universal upper bound for b(n)—one which does not depend on r(n).

Proposition 3.4. If b(n) is an r(n)-bonacci sequence, then b(n) ≤ 2^{n−1} for all n ≥ 1.

Proof. Let r̂(n) = n for all n ≥ 1, and let b̂(n) be the r(n)-bonacci sequence generated by r̂(n). By Lemma 3.3, b̂(n) = 2^{n−1} for all n ≥ 1. Note that b(0) = b̂(0) = 1. Inductively, we have

b(n) = ∑_{k=1}^{r(n)} b(n − k) ≤ ∑_{k=1}^{n} b(n − k) ≤ ∑_{k=1}^{r̂(n)} b̂(n − k) = b̂(n) = 2^{n−1}.

This bound shows that all r(n)-bonacci sequences are O(2^{n}). Hence, their order is at most exponential. We compare the growth rate of b(n) to the growth rate of the r-bonacci numbers.

Proposition 3.5. Let b(n) be an r(n)-bonacci sequence. If r ≤ lim inf_{n→∞} r(n) for some r ∈ ℤ^{+}, then b(n) is Ω(α_{r}^{n}).

Proof. Fix N so that r(n) ≥ r for all n > N. Let r̂(n) = r(n) for n = 0, …, N, and r̂(n) = r for n > N. Let b̂(n) be the r(n)-bonacci sequence generated by r̂(n). For n large, b̂(n) satisfies the r-bonacci recursion, so its tail is a generalized r-bonacci sequence with initial conditions b̂(N + 1), …, b̂(N + r). Hence, b̂(n) is Θ(α_{r}^{n}). It is clear that b̂(n) ≤ b(n) for all n. Therefore, b(n) is Ω(α_{r}^{n}).

We give a condition for b(n) to grow exponentially.

Corollary 3.6. If lim inf_{n→∞} r(n) ≥ 2, then b(n) grows exponentially.

Proof. By Proposition 3.5, b(n) is Ω(α_{r}^{n}) for some r ≥ 2. It is known that α_{r} > 1 for r ≥ 2 [15].

We extend Lemma 3.3 to cover all cases of Δr(n). This yields information about the relative magnitude of b(n)/b(n − 1) and 2. The following is the main lemma in this paper:

Lemma 3.7. For all n ≥ 1 the following hold:

a. b(n)/b(n − 1) = 1 if and only if Δr(n) = 1 − r(n − 1);

b. 1 < b(n)/b(n − 1) < 2 if and only if 1 − r(n − 1) < Δr(n) < 1;

c. b(n)/b(n − 1) = 2 if and only if Δr(n) = 1;

d. b(n)/b(n − 1) > 2 if and only if Δr(n) > 1.

Proof. We will prove the “if” part of each case. Case a is equivalent to r(n) = 1, so it is clear. Case c is Lemma 3.3. In case b, we have r(n) < r(n − 1) + 1. Thus,

b(n) = ∑_{k=1}^{r(n)} b(n − k) < ∑_{k=1}^{r(n−1)+1} b(n − k) = 2b(n − 1),

where the last equality follows from Lemma 3.3. Case d is similar. The “only if” directions follow by considering the above cases.

We use this result on the short-term growth of b(n) to study the long-term growth of b(n).

Corollary 3.8. If lim sup_{n→∞} \frac{b(n)}{b(n − 1)} < 2, then r(n) is eventually constant.

Proof. By Lemma 3.7.b for all n sufficiently large, r(n) − 1 < r(n − 1). It follows that for n large, r(n) is a non-increasing sequence of positive integers, so it is eventually constant.

Lemma 3.9. For any r(n)-bonacci sequence b(n), we have

lim inf_{n→∞} \frac{b(n)}{b(n − 1)} ≤ 2.

Proof. Towards a contradiction, suppose not. By Lemma 3.7.d, for all n sufficiently large, Δr(n) > 1. It follows that n − r(n) < (n − 1) − r(n − 1) for n large. Thus, (n − r(n)) is a strictly decreasing sequence of integers for n large. Therefore, N − r(N) < 0 for some N, contrary to r(n) ≤ n by Definition 1.1.

We now demonstrate the wide range of asymptotic growth rates that are found in the r(n)- bonacci family. For a sequence of real numbers σ(n) that satisfies the following conditions on growth, we can construct an r(n)-bonacci sequence b(n) that grows at the same rate as σ(n) in some sense. In particular, b(n) is Θ(σ(n)).

Theorem 1. Let σ(n) be a sequence of real numbers such that the following hold for all n sufficiently large:

1. σ(n) is non-decreasing;

2. σ(n) ≥ 1;

3. σ(n) ≤ 2^{n−1};

4. σ(n) ≥ σ(n + 1)/2.

Then there is an r(n)-bonacci sequence b(n) such that for all n sufficiently large,

σ(n)/2 < b(n) ≤ σ(n).

Proof. We construct b(n) by using Lemma 3.7 to choose r(n) appropriately. Take N large enough so that σ(n) satisfies all 4 of the above conditions for all n ≥ N. We have 1 ≤ σ(N) ≤ 2^{N−1} by Conditions 2 and 3, so σ(N)/2 < 2^{m} ≤ σ(N) for some m < N. Let r(n) = n for n = 1, …, m, and r(n) = 1 for n = m + 1, …, N. Lemma 3.7 implies that b(N) = b(m) = 2^{m}, so b(N) satisfies the desired bounds.

Suppose now that for some n > N we have defined the sequence up to b(n − 1), so that σ(n − 1)/2 < b(n − 1) ≤ σ(n − 1). We will choose r(n) so that b(n) also satisfies the desired bounds.

If b(n − 1) > σ(n)/2, let r(n) = 1, so b(n) = b(n − 1) and the lower bound is obviously satisfied. For the upper bound, b(n) = b(n − 1) ≤ σ(n − 1) ≤ σ(n) by Condition 1.

Otherwise, we have b(n − 1) ≤ σ(n)/2. Let r(n) = r(n − 1) + 1. By Lemma 3.3, b(n) = 2b(n − 1) ≤ σ(n). Also, b(n) = 2b(n − 1) > σ(n − 1) ≥ σ(n)/2 by Condition 4.

Examples 2.6, 2.7 and 2.8 show the b(n) given by the above construction for σ(n) = \sqrt{3}^{n}, σ(n) = n, and σ(n) = 2 log_{2} n respectively. The conditions on σ(n) are mild. The first two conditions reflect basic properties of the growth of b(n). The last two say that σ(n) does not more than double in either the long term or the short term respectively. Conditions 1–3 are necessary (by Definition 1.1 and Proposition 3.4). Condition 4 is only sufficient and could be weakened. We note three common classes of sequences that can be σ(n).

Corollary 3.10. Let γ ∈ ℝ. The following sequences satisfy the hypotheses of Theorem 1:

1. σ(n) = γ^{n} (1 ≤ γ < 2);

2. σ(n) = n^{γ} (γ ≥ 0);

3. σ(n) = log_{γ} n (γ > 1).

Suppose σ(n) satisfies the conditions of Theorem 1 and σ(n) → ∞. If we allow greater oscillation from b(n), we can construct uncountably many r(n)-bonacci sequences that grow at the same rate as σ(n).

Corollary 3.11. If σ(n) is a sequence that satisfies the hypotheses of Theorem 1 and lim_{n→∞} σ(n) = ∞, then there are uncountably many r(n)-bonacci sequences b(n) such that for all n sufficiently large,

σ(n)/4 < b(n) ≤ σ(n).

Proof. The details of the proof are essentially the same as in Theorem 1. Suppose that we have defined the sequence up to b(n − 1). If b(n − 1) > σ(n)/2, let r(n) = 1. If b(n − 1) ≤ σ(n)/4, let r(n) = r(n − 1) + 1. The interesting case is when σ(n)/4 < b(n − 1) ≤ σ(n)/2. Either of the choices r(n) = 1 or r(n) = r(n − 1) + 1 will result in a b(n) that satisfies the desired bounds. Since σ(n) → ∞, there will be countably many n where we have to make a choice.

We now turn to the question of asymptotic limits of b(n). The possible limits for the short-term growth of b(n), that is the sequence (b(n)/b(n − 1)), are restricted. One possible limit is α_{r}, the growth rate of the r-bonacci numbers.

Lemma 3.12. If lim_{n→∞} r(n) = r, then

lim_{n→∞} \frac{b(n)}{b(n − 1)} = α_{r}.

Proof. For n sufficiently large, b(n) satisfies the r-boncacci recursion or is eventually constant.

If r(n) is not eventually constant, the only possible limit for the short-term growth is 2.

Lemma 3.13. If the sequence (b(n)/b(n−1)) converges and r(n) is not eventually constant, then

lim_{n→∞} b(n)/b(n − 1) = 2.

Proof. Suppose lim sup_{n→∞} b(n)/b(n − 1) < 2. By Corollary 3.8, lim_{n→∞} r(n) = r for some r ∈ ℤ^{+}, contrary to assumption. Thus, lim sup_{n→∞} b(n)/b(n − 1) ≥ 2. By Lemma 3.9, lim inf_{n→∞} b(n)/b(n − 1) ≤ 2. Therefore, the only possible limit for (b(n)/b(n − 1)) is 2.

It is known that α_{r} → 2 [16]. Hence, if the short-term growth rate of b(n) converges, it converges to some α_{r}, or the limiting value of the α_{r}. This restriction on short-term growth leads to a restriction on long-term growth. Particularly, b(n) can converge asymptotically to a restricted class of sequences. Although b(n) can grow at the same rate as a wide variety of sequences, b(n) is a good approximation of a limited class of sequences. While b(n) may grow at the same rate overall as some σ(n), in general b(n) oscillates a great deal. For instance, the sequences constructed by Theorem 1 oscillate between σ(n)/2 and σ(n). This oscillation severely restricts the possible asymptotic limits of b(n).

Theorem 2. Let σ(n) be a sequence of real numbers such that lim_{n→∞} σ(n)/σ(n − 1) exists and is non-zero. If

lim_{n→∞} \frac{b(n)}{σ(n)} = L

with 0 < L < ∞, then

lim_{n→∞} \frac{σ(n)}{σ(n − 1)} = 2, or lim_{n→∞} \frac{σ(n)}{σ(n − 1)} = α_{r}

for some r ≥ 1 and r(n) = r for all n sufficiently large.

Proof. A simple computation gives

\frac{b(n)}{σ(n)} = \frac{b(n)}{b(n − 1)} \frac{b(n − 1)}{σ(n − 1)} \frac{σ(n − 1)}{σ(n)}.

Taking limits we find that

L = ( lim_{n→∞} \frac{b(n)}{b(n − 1)})(L) ( lim_{n→∞} \frac{σ(n − 1)}{σ(n)})
lim_{n→∞} \frac{σ(n)}{σ(n − 1)} = lim_{n→∞} \frac{b(n)}{b(n − 1)}.

The Theorem follows from Lemmas 3.12 and 3.13.

4 Estimates on Growth

In this section, we derive estimates for b(n) in terms of r(n). We gvie a technique to iteratively compute estimates. We recall how one determines the growth rate of r-bonacci sequences. We generalize this technique to cover r(n)-bonacci sequences. We find upper and lower bounds for the short-term growth of r(n)-bonacci numbers. We use these bounds to study long-term growth. We give upper and lower bounds for b(n) that depend only on r(1), …, r(n), and not the previous b(k). As an application of our estimates, we show that the Narayana-Zidek-Capell numbers converge asymptotically. Throughout this section, let b(n) be a variable-r meta-Fibonacci sequence generated by r(n).

We begin by outlining how one shows that the short-term growth rate of the Fibonacci numbers converges to α_{2}. Let α_{2}(n) = f_{n}/f_{n−1}. By the defining recursion of f_{n},

\frac{f_{n}}{f_{n−1}} = 1 + \frac{f_{n−2}}{f_{n−1}} .

We can rewrite this equation in terms of α_{2}(n):

α_{2}(n) = 1 + \frac{1}{α_{2}(n − 1)}.

Let n → ∞. It follows that α_{2}(n) → (1 + \sqrt{5})/2 = α_{2}. A similar argument works for the r-bonacci numbers. However, to show convergence we use that the order of the recursion is constant.

Now consider an r(n)-bonacci sequence b(n). Fix n such that r(n) > 1. We can start in the same manner:

\frac{b(n)}{b(n − 1)} = 1 + ∑_{k=2}^{r(n)} \frac{b(n − k)}{b(n − 1)}.  (1)

In general, the ratios do not converge, but we can use (1) to estimate the growth of b(n). It is useful to write the terms on the right-hand side as telescoping products:

\frac{b(n)}{b(n − 1)} = 1 + ∑_{k=2}^{r(n)} ∏_{j=1}^{k−1} \frac{b(n − j − 1)}{b(n − j)}.  (2)

Notice that we have expressed the ratio b(n)/b(n − 1) in terms of the reciprocal of the ratio of the previous b(n − j)/b(n − j − 1). F. Dubeau used a similar fact in his study of the growth rate of the r-bonacci numbers (α_{r}) [6]. Generalizing Dubeau’s argument, we can use this equation to obtain upper bounds from lower bounds and vice versa.

Lemma 4.1. If for some n > 1, we have r(n) > 1 and

λ(i) ≤ \frac{b(i)}{b(i − 1)} ≤ υ(i),

for i = n − r(n), …, n − 1, then

1 + ∑_{k=2}^{r(n)} ∏_{j=1}^{k−1} \frac{1}{υ(n − j)} ≤ \frac{b(n)}{b(n − 1)} ≤ 1 + ∑_{k=2}^{r(n)} ∏_{j=1}^{k−1} \frac{1}{λ(n − j)}.

Our objective now is to find explicit upper and lower bounds for b(n)/b(n − 1). The following lemma is the basis for many of our other estimates. We relate the short-term growth of b(n) to r(n).

Lemma 4.2. For all n ≥ 1,

\frac{b(n)}{b(n − 1)} ≤ r(n).

Proof. By definition,

b(n) = ∑_{k=1}^{r(n)} b(n − k)

≤ ∑_{k=1}^{r(n)} b(n − 1) since the b(n) are non-increasing,
= r(n) b(n − 1).

The above estimate is sharp. We can let r(1) = ⋯ = r(n − 1) = 1 and r(n) = n for any n > 1. Then b(1) = ⋯ = b(n − 1) = 1, and b(n) = n, so b(n)/b(n − 1) = n = r(n). From the above Lemma, it follows that b(n) ≤ ∏_{k=1}^{n} r(k). Which implies b(n) ≤ n!. Although, from Lemma 3.4 we know in fact that b(n) ≤ 2^{n−1}. Therefore, while Lemma 4.2 gives a sharp estimate of the short-term growth of b(n), in the long term it is highly inaccurate. However, it is good enough for our purposes. We give a lower bound for b(n)/b(n − 1), which depends only on r(n − 1).

Lemma 4.3. If r(n) > 1, then

\frac{b(n)}{b(n − 1)} ≥ 1 + \frac{1}{r(n − 1)}.

Proof. Since r(n) > 1, we can combine Lemmas 4.1 and 4.2 to get

\frac{b(n)}{b(n − 1)} ≥ 1 + ∑_{k=2}^{r(n)} ∏_{j=1}^{k−1} \frac{1}{r(n − j)} ≥ 1 + \frac{1}{r(n − 1)}.

We use Lemma 4.3 to obtain a new upper bound for growth.

Lemma 4.4. If r(k) > 1 for k = n − r(n), …, n, then

\frac{b(n)}{b(n − 1)} ≤ 1 + ∑_{k=2}^{r(n)} ∏_{j=1}^{k−1} \frac{r(n − j)}{1 + r(n − j)} < r(n).

Proof. Combine Lemmas 4.3 and 4.1.

Note that we have obtained a better estimate than we started with. One could certainly find even better estimates. One method is to continue to use Lemma 4.1 to iterate the bounds. Dubeau used a similar technique to good effect in his study of the α_{r} [6].

Definition 4.5. For n ≥ 1, define

ρ(n) = 1 + \frac{1}{r(n − 1)} if r(n) > 1,

and ρ(n) = 1 otherwise.

We give an estimate for b(n) that depends only on ρ(k) (k ≤ n), that is r(1), …, r(n).

Theorem 4.6. For all n ≥ 1,

∏_{k=1}^{n} ρ(k) ≤ b(n) ≤ 1 + ∑_{k=2}^{r(n)} ∏_{j=1}^{k−1} \frac{1}{ρ(k)}.

Proof. Since b(0) = 1, b(n) = b(n)/b(0). So we can write b(n) as a telescoping product:

b(n) = ∏_{k=1}^{n} \frac{b(k)}{b(k − 1)}.

It follows from Lemma 4.3 that ρ(k) ≤ b(k)/b(k − 1) for all k. Applying Lemma 4.1 gives the upper bound.

In the late 1960s, T. V. Narayana, J. Zidek and P. Capell studied the combinatorics of knock-out tournaments. The Narayana-Zidek-Capell sequence (\underline{A002083}) gives the number of knock-out tournaments with n players [3]. According to G. Kreweras, this sequence was originally discovered by M. A. Stern in 1838 [13]. This sequence is an r(n)-bonacci sequence. As an application of the above techniques, we solve an open problem. We show that the Narayana-Zidek-Capell sequence converges asymptotically. We start with a fairly weak upper bound; the ratios of successive terms of the sequence are bounded above by 2. We obtain a lower bound that is sufficiently strong to show asymptotic convergence.

Example 4.7 (The Narayana-Zidek-Capell sequence). Let r(0) = r(1) = 1, and r(n) = ⌊n/2⌋, n > 1:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ r(n) & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ a(n) & 1 & 1 & 1 & 1 & 2 & 3 & 6 & 11 & 22 & 42 & 84 & 165 \end{matrix}

Remark. It is unconventional to define a(0).

The sequence satisfies the recursion relation:

a(2n) = 2 a(2n − 1), a(2n + 1) = 2 a(2n) − a(n), n > 1.  (3)

Narayana and Capell found upper and lower bounds for a(n) [3, p. 108]:

0.625 < \frac{a(n)}{2^{n−3}} < 0.64453125, n ≥ 11.  (4)

G. McGarvey conjectured that lim inf_{n→∞} a(n)/2^{n−3} ≈ 0.633368 (\underline{A002083}):

\begin{matrix}n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ a(n)/2^{n−3} & 2 & 1 & 1 & .75 & .75 & .6875 & .6875 & .65625 & .65625 & .64453 & .64453 & .63867 \end{matrix}

We show that a(n) ∼ c2^{n−3} for some c > 0. We give an explicit estimate for convergence, so the rate of convergence is computable. First, we prove a lower bound for the short-term growth when the index is odd.

Lemma 4.8. For all n ≥ 2,

\frac{a(2n + 1)}{a(2n)} ≥ 2 − \frac{1}{2^{n−1}} .

Proof. From the recursion relation (3), it is immediate that a(k)/a(k − 1) ≤ 2 for all k ≥ 1. We apply Lemma 4.1 to obtain

\frac{a(2n + 1)}{a(2n)} ≥ 1 + ∑_{k=2}^{n} ∏_{j=1}^{k−1} \frac{1}{2} = ∑_{i=0}^{n−1} \frac{1}{2^{i}} = 2 − \frac{1}{2^{n−1}} .

Theorem 4.9. The Narayana-Zidek-Capell sequence converges asymptotically to c2^{n−3} for some positive real number c.

Proof. It suffices to show that a(n)/2^{n} converges to a non-zero limit. Write a(n)/2^{n} as a telescoping product:

\frac{a(n)}{2^{n}} = ∏_{k=1}^{n} \frac{1}{2} \frac{a(k)}{a(k − 1)}.

We use the comparison test to show that the product converges. From the recursion, it is clear that a(n)/2^{n} ≤ 1 for all n. So, we need only consider lower bounds. If k is even, then a(k)/a(k − 1) = 2. Thus, only the terms with odd indices affect the product. We can write

\frac{a(n)}{2^{n}} = ∏_{k=2}^{⌊n/2⌋} \frac{1}{2} \frac{a(2k + 1)}{a(2k)},

since a(3)/a(2) = a(1)/a(0) = 1. Hence, a(2n)/2^{2n} = a(2n + 1)/2^{2n+1}, and it suffices to consider only the odd terms of the product:

\frac{a(2n + 1)}{2^{2n+1}} = ∏_{k=2}^{n} \frac{1}{2} \frac{a(2k + 1)}{a(2k)}.

By Lemma 4.8,

\frac{a(2n + 1)}{2^{2n+1}} ≥ ∏_{k=2}^{n} \frac{1}{2} (2 − \frac{1}{2^{k−1}} ) = ∏_{k=2}^{n} (1 − \frac{1}{2^{k}} ) .

The product on the right-hand side (\underline{A048651}) converges as n → ∞.

5 A Generalization

We define a generalization of b(n), which is a double sequence. This generalization allows us to remove the restriction that r(n) ≤ n. It also allows us to pick different initial conditions for our sequence. This generalization has applications to polynomial dynamics.

Definition 5.1. We call a double sequence β(n), n ∈ ℤ, an extended variable-r meta-Fibonacci sequence if there exists r : ℤ → ℤ^{+} such that for all n ∈ ℤ,

β(n) = ∑_{k=1}^{r(n)} β(n − k).

The author originally discovered r(n)-bonacci numbers while studying the dynamics of complex polynomials [7, 8]. The generalized return times of polynomials are extended r(n)- bonacci numbers, with r(n) = 1 and β(n) = 1 for n ≤ 0. Note that such a β(n) is a non-decreasing sequence of positive integers. We give an example of this type of β(n). For fun, we take r(n) as the Fibonacci numbers for n > 0.

Example 5.2. Let β(n) = 1 and r(n) = 1 for n ≤ 0. Let r(n) = f_{n+1} for n > 0:

\begin{matrix}n & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ r(n) & 1 & 1 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 \\ β(n) & 1 & 1 & 1 & 1 & 2 & 4 & 9 & 20 & 44 & 95 & 202 & 424 \end{matrix}

It is left as an exercise to show that β(n) = 2β(n − 1) + f_{n−1} − 1 for n > 0.

Remark. Certain results in this paper, especially Lemma 4.1, used only the form of the recursion—these results apply immediately to all β(n). Provided that β(n) > 0 for all n ∈ ℤ, many results in this paper apply to β(n), particularly Lemma 3.7. We used the fact that b(n) is non-decreasing in the proof of Lemma 4.2. So, all results that depend on this lemma, require that β(n) be non-decreasing. In particular, all results in Section 4 apply if β(n) non-decreasing and positive. One important difference is that the long-term growth rate of an extended r(n)-bonacci sequence can exceed 2. Therefore, Proposition 3.4, Lemma 3.13 and Theorem 2 do not necessarily apply to extended sequences when we have r(n) > n.

We can generalize Lemma 3.9.

Lemma 5.3. Let β(n) be an extended variable-r meta-Fibonacci sequence generated by r(n). If lim inf_{n→∞} β(n)/β(n − 1) > 2, then Δr(n) ≥ 2 for all n sufficiently large.

It is not clear which double sequences r(n) can generate an extended r(n)-bonacci sequence. We do not attempt to give a complete answer to this question. Instead, we give a class r(n) that work; we require that r(n) be constant for non-positive n. Recall for the Fibonacci numbers, we use f_{n−2} = f_{n} − f_{n−1} to define f_{n} for n ≤ 0. We can define β(n) for n ≤ 0 in an analogous manner. In this case, a closed form of β(n) for n ≤ 0 can be easily found using standard techniques.

Proposition 5.4. Fix R > 0. Let r : ℤ → ℤ^{+} such that r(n) = R for all n ≤ 0. Choose initial conditions β(0), β(−1), …, β(1 − R) ∈ ℝ. First, for n = 0, −1, −2, … define

β(n − R) = β(n) − ∑_{k=1}^{R−1} β(n − k).  (5)

Next, for n ≥ 0 let

β(n) = ∑_{k=1}^{r(n)} β(n − k).

Then β(n) is an extended variable-r meta-Fibonacci sequence generated by r(n).

Proof. We need to check that β(n) is well defined and satisfies the r(n)-bonacci recursion for all n ∈ ℤ. For n ≤ 0, note that β(n) depends only on β(n + 1), …, β(n + R), which have been previously defined, and (5) can be rewritten as the r(n)-bonacci recursion. For n > 0, the only concern is that we may have n − r(n) < 0 for some n, but then β(n − r(n)) was defined in the first step.

We give two examples of the above construction.

Example 5.5. Let r(n) = 2 for n ≤ 0 and r(n) = 2n for n > 0. Choose β(0) = π and β(−1) = 1. Now, we use (5) to compute β(−2) = β(0) − β(−1) = π − 1. Next, compute β(n) for n < −2. Finally, compute β(n) for n positive.

\begin{matrix}n & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 \\ r(n) & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 4 & 6 & 8 \\ β(n) & −3π + 5 & 2π − 3 & −π + 2 & π − 1 & 1 & π & π + 1 & 3π + 1 & 5π + 4 & 12π + 5 \end{matrix}

In the above example, even though the initial conditions are both positive, for n ≤ −2, β(n) alternates between positive and negative values.

Example 5.6. Let r(n) = 3 for n ≤ 0, and r(n) = 2n for n > 0. Choose β(0) = 3, β(−1) = 2 and β(−2) = 1:

\begin{matrix}n & −7 & −6 & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ r(n) & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2 & 4 & 6 & 8 & 10 & 12 \\ β(n) & 2 & −1 & 0 & 1 & 0 & 1 & 2 & 3 & 5 & 11 & 22 & 45 & 90 & 179 \end{matrix}

Lemma 3.7 does not apply to the above sequence, because not all of the terms are positive. Note that Δr(3) = 2, but β(3)/β(2) = 2. Even worse, Δr(6) = 2, but β(6)/β(5) < 2.

6 Acknowledgements

Jeffrey Shallit was kind enough to point out that the Narayana-Zidek-Capell sequence (\underline{A002083}) can be obtained as an r(n)-bonacci sequence.

I would like to thank the anonymous referee for his useful comments.

References

[1] Bodil Branner and John Hubbard, Iteration of cubic polynomials, part II: Patterns and parapatterns, Acta Math. 169 (1992), 229–325. MR 1194004

[2] Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM J. Discrete Math. 18 (2004), 794–824. MR 2157827

[3] P. Capell and T. V. Narayana, On knock-out tournaments, Canad. Math. Bull., 13 (1970), 105–109. MR 0264997

[4] B. W. Conolly, Meta-Fibonacci sequences, ch. XII of Fibonacci & Lucas Numbers and the Golden Section, by S. Vajda, pp. 127–138, Ellis Horwood, 1989. MR 1015938

[5] R. Dawson, G. Gabor, R. Nowakowski, and D. Wiens, Random Fibonacci-type sequences, Fibonacci Quart. 23 (1985), 169–176. MR 797140

[6] Dubeau, François, On r-generalized Fibonacci numbers, Fibonacci Quart., 27 (1989), 221–229. MR 1002065

[7] Nathaniel D. Emerson, Dynamics of polynomials whose Julia set is an area zero Cantor set, Ph. D. thesis, University of California Los Angeles, 2001.

[8] Nathaniel D. Emerson, Return times of polynomials as meta-Fibonacci numbers, Preprint, August 2005.

[9] Richard K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186–190. MR 1540817

[10] Douglas R. Hofstader, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, 1979.

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

[12] Brad Jackson and Frank Ruskey, Meta-Fibonacci sequences, binary trees, and extremal compact codes, preprint, April 2005.

[13] G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, Math. Sci. Humaines 84 (1983), 45–63. MR 0734845

[14] Colin L. Mallows, Conway’s challenge sequence, Amer. Math. Monthly 98 (1991), 5–20. MR 1083608

[15] E. P. Miles, Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752. MR 0123521

[16] Lawrence Somer, Problem H-197 (and Solution), Fibonacci Quart. 12 (1974), 110–111.

[17] Stephen M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discr. Math. 105 (1992), 227–239. MR 1180206

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11B99. Keywords: Meta-Fibonacci, Hofstadter sequence, Narayana-Zidek-Capell sequence.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A002083}, \underline{A004001}, \underline{A005185}, \underline{A006949} and \underline{A092921}.)

Received September 13 2005; revised version received March 17 2006. Published in Journal of Integer Sequences, March 17 2006.

Return to Journal of Integer Sequences home page.