The mysterious behavior of "meta-Fibonacci" sequences

Frank Ruskey

University of Victoria

Abstract

This talk is concerned with the enigmatic behavior of nested recurrence relations of the form A(n) = A(n - s - A(n - a_1 ) - ... - A(n - a_p )) + A(n - s - t - A(n - b_1 ) - ... - A(n - b_p )) where 0 \leq s, 0 \leq t, a_1 \leq ... \leq a_p, and b_1 \leq ... \leq b_p. Examples include Hofstadter's famous Q sequence (p = q = 1, s = t = 0, a1 = 1, b1 = 2; from Gödel, Escher, and Bach) and the Conolly meta-Fibonacci o recurrence A(n) = A(n - A(n - 1)) + A(n - 1 - A(n - 2)). In