The number of valid factorizations of Fibonacci prefixes

Abstract: 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 strictly) decreasing sequence of standard Fibonacci words. In particular, we show that the sequence V(n) is the shuffle of the ceilings of two linear functions of n.

Review text

The sequence \((f_n)\) of finite Fibonacci words over the binary alphabet \(\{a,b\}\) is defined by the recurrence \(f_{n+1}=f_n f_{n-1}\) for \(n=1,2\dots\), starting with \(f_0=a\) and \(f_1=ab\). The infinite Fibonacci word \(\mathbf{f}\) is the limit of this sequence as \(n\) tends to infinity. The authors compute the number of factorizations of the length-\(N\) prefix of \(\mathbf{f}\) into a (not strictly) decreasing sequence of finite Fibonacci words. Their main result (Theorem 1) shows that this number is equal to \(\lceil N/\varphi^2\rceil\) if the prefix ends with \(a\) and equal to \(\lceil N/\varphi^3\rceil\) if the prefix ends with \(b\); here \(\varphi\) stands for the golden ratio \(\frac{1+\sqrt{5}}2\).

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: The number of valid factorizations of Fibonacci prefixes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419114)