Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Linear-Recurrent Solutions to Meta-Fibonacci Recurrences
Speaker: Nathan Fox, Rutgers University
Date: Thursday, October 1, 2015 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
In 1963, Douglas Hofstadter first contemplated the recurrence Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)). He found that, when given the initial conditions Q(1)=1 and Q(2)=1, this sequence behaves chaotically. In fact, we still do not know whether Q(n) < n for all n. About thirty years later, Solomon Golomb observed that the initial conditions Q(1)=3, Q(2)=2, Q(3)=1 give rise to a much more predictable sequence. Even more recently, Frank Ruskey discovered a way to embed the Fibonacci sequence into the Hofstadter's recurrence. In this talk, we will expand upon the ideas of Golomb and Ruskey as we explore what sorts of nice solutions exist to the Hofstadter and related recurrences, known as meta-Fibonacci recurrences.