A Combinatorial Problem Solved by a Meta-Fibonacci Recurrence Relation

Abstract

We present a natural, combinatorial problem whose solution is given by the meta-Fibonacci recurrence relation $a(n)={\sum }_{i=1}^{p}a(n-i+1-a(n-i))$, where $p$ is prime. This combinatorial problem is less general than those given in [3] (B. Jackson, F. Ruskey, 2006) and [4] (F. Ruskey, C. Deugau, 2009), but it has the advantage of having a simpler statement.