Discrete Mathematics and Optimization Seminar
Mar. 11th, 2009
MC 320 - 4:00 PM
Meta-Fibonacci Recursions: Hofstadter, Conolly and Much More
Steve Tanny
University of Toronto
The study of integer sequences defined by meta-Fibonacci recursions (also called ''self-referencing'' or ''nested'' recursions) is a promising new field that has grown in the last thirty years from a brief mention in Hofstadter book ''Godel, Escher, Bach: An Eternal Golden Braid'' to dozens of papers by mathematicians around the world. In these recursions the arguments in the function defining the sequence depend upon earlier values of the sequence itself.

In this talk we provide some general background on these recursions. We then discuss various generalizations of the Conolly meta-Fibonacci recursion, defined by C(n) = C(n-C(n-1)) + C(n-1-C(n-2)), with initial conditions C(1) = C(2) =1. Our focus is on variants of the Conolly recursion, together with their corresponding initial conditions, that generate sequences that are ble to derive a fascinating and unexpected combinatorial interpretation for such sequences: we show that they count the number of leaves in certain sub-trees of infinite trees, including binary trees, with special labeling schemes.