MIT Combinatorics Seminar

Combinatorial Properties of the Stern Sequence

Bruce Reznick (University of Illinois at Urbana-Champaign)

Wednesday, March 22, 2006   4:30 pm    Room 2-105

## ABSTRACT

In this talk, we will survey some old and new results about the Stern sequence, a highly underappreciated mathematical object. 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 "diatomic" 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; as one final example, s(729) = 64.