Abstract:

This paper is concerned with a family of $k$-ary meta-Fibonacci sequences described by the recurrence relation

$$a(n) = \sum_{i=1}^k a(n{-}i - (s{-}1) - a(n{-}i)),$$

where $s$ may be any integer, positive or negative. If $s \ge 0$, then the initial conditions are $a(n) = 1$ for $1 \le n \le s+1$ and $a(n) = n-s$ for $s+1 < n \le s+k$. If $s \le 0$, then the initial conditions are $a(n) = n$ for $1 \le n \le k(-s+1)$. We show that these sequences arise as the solutions of two natural counting problems: The number of leaves at the largest level in certain infinite $k$-ary trees, and (for $s \ge 0$) certain restricted compositions of an integer. For this family of generalized meta-Fibonacci sequences and two families of related sequences we derive combinatorial bijections, ordinary generating functions, recurrence relations, and asymptotics ( $a(n) \sim n(k-1)/k$). We also show that these sequences are related to a ``self-describing" sequence of Cloitre and Sloane.