Hofstadter-like Sequences over Nonstandard Integers (part 1)

Nathan Fox, Rutgers Experimental Mathematics Seminar, November 10, 2016

See part 2 at vimeo.com/191094181

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.