Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Curious Patterns and Nonpatterns in a Family of Meta-Fibonacci Recursions
Speaker: Douglas Hofstadter, Cognitive Science, Indiana University
Date: Thursday, April 10, 2014 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In 1963, while playing a novel number-theoretical game with a friend, I dreamt up a curious recursive definition for an integer-valued function, which I dubbed "Q(n)". Here is the recursion:
Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))
The two initial values I supplied were Q(1) = 1 and Q(2) = 1. This function's behavior turned out to be very unpredictable. I spent a good deal of time exploring it computationally, and also invented and explored some variations on the theme. To my frustration, though, I wasn't able to prove anything about Q(n) (not even that it existed for all positive values of n!), no matter how hard I worked. Eventually, as often tends to happen when one has pushed oneself as far as one can go and has hit up against one's limits, Q(n) slowly faded into the background of my life. Many years later, my mathematician/physicist friend Greg Huber proposed that we go back to the canonical and very natural but unsolved questions about the mysterious function Q(n), with its magnetic appeal and crystalline beauty, and carefully study them. I went for Greg's bait hook, line, and sinker, but soon I found, to my great frustration, that unlike Greg, who had made some small progress analytically, I was completely unable to prove anything analytically about Q(n). Soon Greg found himself in a similar position of frustration. After a period of stagnation, finding ourselves in a box canyon with no escape route except using a computer to do experimental mathematics, together he and I invented a two-parameter family of functions closely related to Q(n) and we explored their behavior computationally. We found some delightful surprises and some deep insights. However, despite all the progress, a lot of mystery remained (and still remains). In this talk, I will mainly describe Greg Huber's and my collaborative discoveries.