Spot-Based Generations for Meta-Fibonacci Sequences

Abstract

For many meta-Fibonacci sequences it is possible to identify a partition of the sequence into successive intervals (sometimes called blocks) with the property that the sequence behaves “similarly” in each block. This partition provides insights into the sequence properties. To date, for any given sequence, only ad hoc methods have been available to identify this partition. We apply a new concept—the spot-based generation sequence—to derive a general methodology for identifying this partition for a large class of meta-Fibonacci sequences. This class includes the Conolly and Conway sequences and many of their well-behaved variants, and even some highly chaotic sequences, such as Hofstadter's famous Q-sequence.

2000 AMS Subject Classification:

• Primary 11B37
• Secondary 39A99

Keywords:

• Connolly sequence
• Conway sequence
• meta-Fibonacci sequence
• spot-based generation
• spot function

ACKNOWLEDGMENTS

We thank Brian Choi and Sahir Haider for their comments on the μ sequence. We would also like to acknowledge the computational assistance of Biao Zhou and Yin Xu on the Q-sequence.

Notes

See, for example, [Callaghan et al. 05], where block structure insights are used to help identify and formulate the appropriate approach and specific induction assumptions required to prove the behavior of a family of sequences related to (1−1).

If it fails, then for the smallest integer n for which it fails, we say that the sequence terminates at index n.

In general, this value of r will be greater than the minimum value that is required by the specific nature of the recurrence (2–2); further, this minimum value can differ for different values of p.

We often refer to M_p (n) as the generation structure for T(n) based on spot p, especially when we are considering the overall characteristics of this sequence rather than the behavior of individual terms.

The interested reader may contact us for additional details.

The transition points double for generations 2 through 10, as does the value of Q(n) at each of these nine points, these values being the first occurrences of 2, …, 2⁹ respectively. This pattern fails for the start point of the 11th Pinn generation.

Observe the typographical error in [Pinn 99, p. 8], where he writes ⌊2 ^g+1/2⌋.

This is done via a careful examination of the behavior of the sequence Q(n)−n/2. The interested reader may contact us for details.