DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Matthew Russell, Rutgers University, russell2 {at} math [dot] rutgers [dot] edu)

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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

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.

See: http://www.math.rutgers.edu/~russell2/expmath/