The Mantovanelli-Hofstadter Sequence

2026/04/04 by Benoit Cloitre
Mathematics · #math.NT

paper · pdf

Abstract

We study the perturbed Hofstadter recurrence introduced by Mantovanelli, \widetildeQ(n)=\widetildeQ(n-\widetildeQ(n-1))+\widetildeQ(n-\widetildeQ(n-2))+(-1)ⁿ, with \widetildeQ(1)=\widetildeQ(2)=1. We prove that this recurrence is well-defined for every positive integer and that lim_n→∞\widetildeQ(n)/n=1/2. We establish the optimal order \widetildeQ(n)=n/2+O(n/√(log n)) and give explicit positive lower and upper bounds for the corresponding normalized limsup. The proof is primarily combinatorial. An odd-even split turns the recurrence into two exact interleavings of binary words, and the resulting Dyck paths define plane forests. Catalan numbers also arise in the enumeration.

Cited by

• Certified Return-Word Induction for a Perturbed Hofstadter Recursion
• A Dyadic Frequency Law for a Perturbed Hofstadter Q-Recursion

Related

• Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation
• A Slow Relative of Hofstadter's Q-Sequence
• A Dyadic Frequency Law for a Perturbed Hofstadter Q-Recursion
• The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions
• A New Approach to the Hofstadter Q-Recurrence