DIMACS - Graduate Student Combinatorics Seminar

Title: Recurrences that Generate Surprising Numbers

Speaker: Emilie Hogan, Rutgers University

Date: Wednesday, October 14, 2009 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


The most basic type of recurrence is a linear recurrence (e.g., Fibonacci). These types of recurrences generate integers, but this is not surprising. In order to get integers in an unexpected way you must consider non-linear recurrences. A well known example of a non-linear recurrence is the Somos-4 recurrence. In order to get the n^th number in the sequence you must take some combination of the n-1st, n-2nd, and n-3rd numbers and then *divide* by the n-4th number. Even though we divide, we still get integers. I will talk about this phenomenon generally and give a few other examples. Finally I will introduce the concept of a recurrence that does not generate a sequence, but instead generates multiple values at each step by solving a degree n polynomial. In this situation it becomes surprising that we generate rational numbers.