*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.

## No comments:

## Post a Comment