Monday, June 20, 2016

Meta recurrences

In my freshman year at college, my roommate Joe introduced me to the book "GĂ¶del, Escher, Bach: an Eternal Golden Braid" by Douglas Hofstadter that I really enjoyed reading.  In this book, Hofstadter considers sequences whose recurrence relation is such that the arguments themselves depend on the terms of the sequence.  For instance, the classical Fibonacci sequence is defined by f(n) = f(n-1) + f(n-2), with f(1) =  f(2) = 1.  Hofstadter considered a meta Fibonacci sequence defined by q(1) = q(2) = 1, and q(n) = q(n-q(n-1)) + q(n-q(n-2)).  Not much is known about this sequence, except that it behaves wildly.  It is not even known whether the sequence is well defined!
Several variants of meta Fibonacci sequences have been analyzed in Refs. [1-4].

For some simpler meta recurrences, much more can be said about them. For instance Golomb showed that sequences satisfying the recursion a(n) = a(n - a(n-1)) is eventually periodic when it is well-defined. He also showed several meta recurrences with explicit solutions, such as a(n) = a(a(n)).
In particular, he showed that the recursion a(n) = a(n-a(n-1)) + 1 with a(1) = 1 has a simple solution described by the sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ....

Next we show that this last recursion can be generalized as follows. For an integer k, define the meta recurrence a(n) = a(n-a(n-k))+k with initial conditions a(i) = i for i = 1,...,k.  This recurrence has a simple solution and it can be constructed starting with km copies of k(m+1), followed by km+1, km+2, ..., k(m+1), as m varies from 0, 1, 2, ... It is straightforward to verify that this construction satisfies the recurrence relation. Thus for each k the sequence corresponding to the meta recurrence is well defined, every positive integer is in the sequence, and every integer not a proper multiple of k appears once. If t is a multiple of k, then t appears t-k+1 times.

The cases of k=2 and k=3 are shown in OEIS sequences A193358 and A274213 respectively.

For k = 4, the sequence is: 1, 2, 3, 4, 8, 8, 8, 8, 5, 6, 7, 8, 12, 12, 12, 12, 12, 12, 12, 12, 9, 10, 11, 12, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 13, 14, 15, 16, ....

References
[1] S.M Tanny "A well-behaved cousin of the Hofstadter sequence," Discrete Math., 105 (1992), pp. 227–239.
[2] Callaghan, Joseph, John J. Chew III, and Stephen M. Tanny. "On the behavior of a family of meta-Fibonacci sequences." SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824.
[3] B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
[4] C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12.