On minimal words with given subword complexity (Q1392298)

Summary: We prove that the minimal length of a word \(S_n\) having the property that it contains exactly \(F_{m+2}\) distinct subwords of length \(m\) for \(1\leq m\leq n\) is \(F_n+ F_{n+ 2}\). Here \(F_n\) is the \(n\)th Fibonacci number defined by \(F_1=F_2=1\) and \(F_n=F_{n-1}+ F_{n-2}\) for \(n>2\). We also give an algorithm that generates a minimal word \(S_n\) for each \(n \geq 1\).