##
**
On the Behavior of a Variant of Hofstadter's Q-Sequence
**

###
B. Balamohan, A. Kuznetsov and Stephen Tanny

Department of Mathematics

University Of Toronto

Toronto, Ontario M5S 2E4

Canada

**Abstract:**

We completely solve the meta-Fibonacci recursion
*V*(*n*) = *V*(*n* - *V*(*n* - 1)) + *V*(*n* - *V*(*n* - 4)),
a variant of Hofstadter's meta-Fibonacci
*Q*-sequence. For the initial conditions *V*(1) = *V*(2) = *V*(3) = *V*(4) =
1 we prove that the sequence *V*(*n*) is monotone, with successive terms
increasing by 0 or 1, so the sequence hits every positive integer. We
demonstrate certain special structural properties and fascinating
periodicities of the associated frequency sequence (the number of times
*V*(*n*) hits each positive integer) that make possible an iterative
computation of *V*(*n*) for any value of *n*. Further, we derive a
natural partition of the *V*-sequence into blocks of consecutive terms
("*generations*") with the property that terms in one block
determine the terms in the next. We conclude by examining all the other
sets of four initial conditions for which this meta-Fibonacci recursion
has a solution; we prove that in each case the resulting sequence is
essentially the same as the one with initial conditions all ones.

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequences
A004001,
A005185
A063882, and
A087777
.)

Received April 11 2007;
revised version received June 26 2007.
Published in *Journal of Integer Sequences*, June 27 2007.

Return to
**Journal of Integer Sequences home page**