The Thue-Morse sequence is a triple-free element $(a\_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.


The beginning of the sequence reads $0110100110010110\dots$


I would like a lower bound on the cardinality of the set of consecutive length $n$ subsequences, $\{a\_ia\_{i+1}\dots a\_{i+n-1}|i\in\mathbb{N}\}$.


For instance, does it grow exponentially in $n$?


By [Cube-free infinite binary words](https://mathoverflow.net/questions/61373/cube-free-infinite-binary-words) the number of length $n$ cube-free words in $\{0,1\}^\mathbb{N}$ grows exponentially in $n$, but is this already true for subsequences of the Thue-Morse sequence?



Counting triple-free sequences
The number of distinct consecutive subwords of length $n$ in the Thue-Morse sequence is actually bounded above by a linear function in $n$.


In fact, there is an explicit formula to count this found independently in these three papers:


[S.V. Avgustinovich, The number of different subwords of given length in the Morse–Hedlund sequence, Sibirsk. Zh. Issled. Oper. 1 (1994)](http://link.springer.com/chapter/10.1007/978-94-009-1606-7_1)


[S. Brlek, Enumeration of factors in the Thue–Morse word, Discrete Appl. Math. 24 (1989) 83–96](http://www.sciencedirect.com/science/article/pii/0166218X9290274E)


[A. de Luca, S. Varricchio, Some combinatorial properties of the Thue–Morse sequence and a problem in semigroups, Theoret. Comput. Sci.
63 (1989) 333–348.](http://www.sciencedirect.com/science/article/pii/0304397589900133)


