How many binary sequences do not contain three consecutive identical blocks of numbers?

112 Views Asked by At

To clarify, here are examples of binary sequences that contain three consecutive identical blocks of numbers:
$\color{red}{111}$
$101\color{red}{000}01$
$00\color{red}{100100100}011$

There are exactly $6$ binary sequences that do not contain two consecutive identical blocks of numbers:
$0$
$1$
$01$
$10$
$010$
$101$

My question is (again), how many binary sequences do not contain three consecutive identical blocks of numbers? I know there are $2$ such sequences of length $1$; $4$ such sequences of length $2$; $6$ such sequences of length $3$; $10$ such sequences of length $4$. But for greater lengths, I do not know how to count the number of such sequences. I presume that beyond a certain length, there are no such sequences.

(According to another question, which inspired this question, there are an infinite number of binary sequences that do not contain $six$ consecutive identical blocks of numbers. I also wonder how many binary sequences do not contain four, or five, consecutive identical blocks of numbers; but one question at a time.)

1

There are 1 best solutions below

2
On BEST ANSWER

Shortly after posting my question, I found the answer: infinite, because the Thue-Morse sequence is cubefree and arbitrarily long.