Title: Nice Solutions to Meta-Fibonacci Recurrences
Speaker: Nathan Fox, Rutgers University
Date: Wednesday, October 21, 2015 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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. This talk will be similar to my October 1 talk at the Experimental Math Seminar, but there will be differences. In particular, that talk was more concerned with giving an overview. Here, we will examine particular results and give more examples.