Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Hofstadter-like Sequences over Nonstandard Integers
Speaker: Nathan Fox, Rutgers Universtiy
Date: Thursday, November 10, 2016 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Hofstadter Q-sequences is defined by the recurrence Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) with the initial conditions Q(1)=1 and Q(2)=1. Despite its simple definition, almost nothing has been proved about this sequence. Most notably, we still do not know whether Q(n) even exists for all n, i.e. if the sequence is infinite or if it "dies." On the other hand, many related sequences are known either to die or not to die. In this talk we will explore some variants of the Hofstadter Q-sequence, and we will describe a method for proving that certain infinite families of sequences all die. This method will involve constructing sequences whose indices and values can be nonstandard integers, which are "integers" that are larger than any natural number.