
Discrete Mathematics and Optimization Seminar

Mar. 11th, 2009 MC 320  4:00 PM
MetaFibonacci Recursions: Hofstadter, Conolly and Much More
Steve Tanny
University of Toronto

The study of integer sequences defined by metaFibonacci recursions (also called ''selfreferencing'' 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 metaFibonacci recursion, defined by C(n) = C(nC(n1)) + C(n1C(n2)), 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 subtrees of infinite trees, including binary trees, with special labeling schemes.



