On a Family of Nested Recurrences and Their Arithmetical Solutions

A family of nested recurrence relations a (n+1) = n - a^ (m) (n) + a^ (m+1) (n), parameterized by an integer m 1 with initial condition a (1) =1, is studied. We prove that a (n) =n-h (n) is the unique solution satisfying this condition, where h (n) is an arithmetical sequence in which each non-negative integer k appears mk+1 times, with h (n) 1-indexed such that h (1) =0. An explicit floor formula for h (n) (and thus for a (n) ) is derived. The proof of the main theorem involves establishing a key identity for h (n) that arises from the recurrence; this identity is then proved using arithmetical properties of h (n) and the iterated function a^ (m) (n) at critical boundary points. Combinatorial interpretations for a (n) and its partial sums (for m=2), and connections to The On-Line Encyclopedia of Integer Sequences (OEIS), including generalizations of Connell's sequence, are also discussed.