The number of valid factorizations of Fibonacci prefixes (Q2419114)

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