The number of valid factorizations of Fibonacci prefixes

Pierre Bonardo, Anna E. Frid, Jeffrey Shallit

We establish several recurrence relations and an explicit formula for V(n), the number of factorizations of the length-n prefix of the Fibonacci word into a (not necessarily strict…