Abstract

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

a(n) = ∑_{i=1}^{k} a(n−i − (s−1) − a(n−i)),

where s may be any integer, positive or negative. If s ≥ 0, then the initial conditions are a(n) = 1 for 1 ≤ n ≤ s + 1 and a(n) = n − s for s + 1 < n ≤ s + k. If s ≤ 0, then the initial conditions are a(n) = n for 1 ≤ n ≤ 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 ≥ 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) ∼ n(k − 1)/k). We also show that these sequences are related to a “self-describing” sequence of Cloitre and Sloane.