Abstract: In this talk, we survey some old and new results about the Stern sequence, a highly underappreciated mathematical object. It is defined by the recurrence s(2n) = s(n) and s(2n+1) = s(n) + s(n+1), with s(0) = 0 and s(1) = 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 2r \le n \le 2r+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 ordered pair (a,b) of relatively prime positive integers 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 rth row is the (r+2)-nd Fibonacci number. The entries in the rth row sum to 3r + 1; the sum of the cubes of the entries is 9*7r-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) is 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.
This talk will be rather elementary and accessible to alert undergraduates.