Nathan Fox, Rutgers University

Abstract

Conolly's sequence (A046699) is defined by the nested recurrence relation C(n)=C(n-C(n-1))+C(n-1-C(n-2)) and the initial conditions C(1)=C(2)=1. This sequence is monotone increasing with each positive integer appearing at least once, a property known in the literature as slow. Conolly's sequence and several other slow sequences generated by nested recurrences are known to have combinatorial interpretations in terms of enumerating leaves in infinite tree structures. For the Conolly sequence, the tree-based interpretation illuminates an intimate connection between the sequence and the powers of two. In fact, the Conolly sequence has an alternate, purely number-theoretic definition based on powers of two. Replacing powers of two with Fibonacci numbers in this construction yields a different slow sequence (A316628). In this talk, we will describe the three different ways of constructing the Conolly sequence (recurrence, number theory, trees) and show why they all yield the same sequence. Then we will construct this new sequence based on the Fibonacci numbers, which also is slow, has a tree-based interpretation, and satisfies a nested recurrence. If time permits, we will describe how to generalize the construction to discover many new integer sequences.