The Stern Sequence

09/20/2011 - 12:15pm
09/20/2011 - 1:10pm
Bruce Reznick (University of Illinois at Urbana Champaign)

In this talk, we will survey some old and new results about the Stern sequence, a highly underappreciated mathematical object from the 19th century. It is defined by the recurrence s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n+1) = s(n) + s(n+1). It is most easily written by imagining a Pascal triangle "with memory", and starting with (1,1). The rows of the resulting array give s(n) for 2^r \le n \le 2^(r+1): (r=0): 1 1 (r=1): 1 2 1 (r=2): 1 3 2 3 1 (r=3): 1 4 3 5 2 5 3 4 1 Stern himself proved in 1858 that every pair of relatively prime positive integers (a,b) occurs exactly once as the pair (s(n),s(n+1)), and the binary representation of n is encoded by the continued fraction representation of a/b. The maximum values in the r-th row is the (r+2)-nd Fibonacci number. The sum of the entries in the r-th row is 3^r + 1; the sum of the cubes of the entries is 9*7^(r-1) for r > 0. The Stern sequence also has many interesting divisibility properties: s(n) is even iff n is a multiple of 3; the set of n for which s(n) is a multiple of 3 has a simple recursive description. The set of n for which s(n) is a multiple of the prime p has density 1/(p+1). Further, s(n) counts the number of binary representations of n-1, if one allows digits from {0,1,2}. If n is odd and m is the integer whose base 2 representation is the reversal of n's, then s(n) = s(m) and s(n+1)s(m+1) = 1 mod (s(n)). The Stern sequence affords a clear understanding of the alluringly-named Minkowski ?-function, which gives a strictly increasing map from [0,1] to itself, taking the rationals to the dyadic rationals, and the quadratic irrationals to the non-dyadic rationals. There are few other mathematical objects which are as generous in their grooviness; for example, s(729) = 64.

Millikan 134 (Pomona College)