The Combinatorics of Certain k-ary Meta-Fibonacci Sequences

This paper is concerned with a family of

-ary meta-Fibonacci sequences described by the recurrence relation

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

where

may be any integer, positive or negative. If $s \ge 0$ , then the initial conditions are

for $1 \le n \le s+1$ and

for $s+1 < n \le s+k$ . If $s \le 0$ , then the initial conditions are

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

-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.

Received March 24 2009; revised version received May 1 2009. Published in Journal of Integer Sequences, May 12 2009.

The Combinatorics of Certain k-ary Meta-Fibonacci Sequences

Frank Ruskey and Chris Deugau University of Victoria Victoria, BC V8W3P6 Canada

Frank Ruskey and Chris Deugau
University of Victoria
Victoria, BC V8W3P6
Canada