Nested recurrence relations are any recurrence relation where at least one of the arguments is dependent
on a previous term. For example, the most famous nested recurrence relation is Hofstadter’s Q-recurrence,
which is defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)) with initial conditions Q(1) = Q(2) = 1.
Research surrounding these types of recurrences often relates to finding solutions, which would mean there
exists an infinite sequence that satisfies the recursion. Hofstadter’s Q-recurrence remains quite mysterious,
and many major properties are not known. Other recurrence relations, many of which are closely related to
the Q-recurrence, have been solved and their properties have been thoroughly examined. Solutions to these
recurrence relations may be classified as slow, periodic, or quasi-periodic, each classification bringing about
different characteristics. Altering initial conditions of different sequences can also bring about sometimes
dramatic changes. An interesting method of finding solutions and exploring nested recurrence relations
involves relating them to infinite labeled trees. The first sequence for which a combinatorial interpretation
was found is the Conolly sequence, defined by C(n) = C(n − C(n − 1)) + C(n − 1 − C(n − 2)) with
C(1) = 1, C(2) = 2. This sequence, as opposed to the Q-recurrence, has much greater structure and concrete
properties.
