CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Nested Recurrence Relations
Organizer and Chair: Frank Ruskey (University of Victoria)

MARCEL CELAYA, McGill University
Morphic Words and Nested Recurrence Relations  [PDF] [SLIDES]

In "G\"odel, Escher, Bach: An Eternal Golden Braid," Douglas Hofstadter introduces his famous recurrence $G(n)=n-G(G(n-1))$ with $G(1)=1$. He writes of his surprising discovery of a highly structured infinite tree generated by the values of $G(n)$.

We introduce a new family of nested recurrences which generalize Hofstadter's $G$ sequence. We analyze these recurrences by recasting his tree interpretation in terms of morphic words over a countable alphabet and applying known results on such words. We present some intriguing examples, and make connections to some well-known sequences including the Conolly and Tanny sequences and the Thue-Morse sequence. (Joint work with Frank Ruskey)

MUSTAZEE RAHMAN, University of Toronto
Nested Recursions, Simultaneous Parameters and Tree Superpositions  [PDF] [SLIDES]

We apply a tree-based methodology to solve certain families of nested recursions of the form $R(n)=\sum_{i=1}^kR(n-a_i-\sum_{j=1}^{p}R(n-b_{ij}))$, where $k$ and $p$ denote "arity" and "order", respectively. Our method associates such recursions with counting leaves of certain infinite labelled trees. We characterize some recursions within $R(n)$ by introducing "simultaneous parameters" that appear both within the recursion and that also specify structural properties of the corresponding tree. We extend and unify results concerning two well known families of arity $k=2$, order $p=1$ recursions. We also solve new recursion families for arity $k=2$ and general order $p$ by applying tree superpositions of simpler trees.

FRANK RUSKEY, University of Victoria
An undecidable nested recurrence relation  [PDF] [SLIDES]

A nested recurrence relation $A(n)$ is undecidable if there is no algorithm that takes as input a finite set of initial conditions and which then correctly determines whether the recurrence relation is well-defined for all natural numbers. By well-defined we simply mean that the sequence $A(1), A(2), \ldots$ can be computed indefinitely, without ever referring to some value that was not determined previously. We show that

\[ A\left(n\right) = A\left(n-4-A\left(A\left(n-4\right)\right)\right)+4A\left(A\left(n-4\right)\right) +A\left(2A\left(n-4-A\left(n-2\right)\right)+A\left(n-2\right)\right) \]

is undecidable. (Joint research with Marcel Celaya.)

JEFF SHALLIT, University of Waterloo
Automata and nested recurrences  [PDF] [SLIDES]

In this talk I will discuss an application of automata to the analysis of nested recurrences. In particular, I'll show that the frequency sequence $F(n)$ of the Balamohan-Kuznetsov-Tanny sequence $V(n)$ defined by $V(n) = 1$ for $n \leq 4$ and $V(n) = V(n-V(n-1)) + V(n-V(n-4))$ otherwise, is 2-automatic.

STEVE TANNY, University of Toronto
An Invitation to Nested Recurrence Relations  [PDF] [SLIDES]

A nested recurrence relation is any recursion where some argument contains a term of the recursion. The study of nested recurrence relations is an exciting new field that has grown very substantially over the last thirty-five years from its early origins as a brief mention in Hofstadter's book Godel, Escher, Bach: An Eternal Golden Braid.

I will provide a broad introduction to, and overview of, this field, highlighting the key milestones in the course of its development.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland