TY - JOUR
TI - An exploration of nested recurrences using experimental mathematics
DO - https://doi.org/doi:10.7282/T3WD43FW
PY - 2017
AB - Broadly speaking, Experimental Mathematics is the philosophy that computers are a valuable tool that should be used extensively in mathematical research. Here, we apply this philosophy to the study of integer sequences arising from nested recurrence relations. The most widely studied nested recurrence is the Hofstadter Q-recurrence: Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)). Hofstadter considered this recurrence with the initial condition Q(1) = Q(2) = 1, and the resulting sequence has much apparent structure. But, almost nothing has been rigorously proved about it. Others have modified the recurrence, the initial conditions, or both, to obtain related but more predictable sequences. We follow that vein and prove a number of unrelated theorems about sequences resulting from nested recurrences. Our first results relate to automatically finding (with proof) solutions to nested recurrences that are interleavings of linear-recurrent sequences. We then present a new nested-recurrent sequence whose terms increase monotonically with successive differences zero or one. Finally, we embark on an exploration of strange but predictable behaviors that result when recurrences are given various types of initial conditions.
KW - Mathematics
KW - Sequences (Mathematics)
LA - eng
ER -