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 general, the sequences are quite sensitive to the initial conditions, and may become undefined. Sometimes the solutions correspond to counting certain combinatorial objects and nice explicit expressions, generating functions, and asymptotics can be obtained. In other cases the true behavior does not be come apparent until n is "large." And in many cases the behavior appears to be somewhat chaotic, with predictable trends, but hard to describe exact values. This is joint research with Brad Jackson (San Jose State U.) and Steve Tanny (U. Toronto).