Sequence of $0$’s and $1$’s without six consecutive identical blocks

Let $$S_n$$ be the number of sequences of $$n$$ zeroes and ones such that the sequence does not contain six consecutive identical blocks of numbers. Show that $$S_n$$ tends to infinity as $$n\to\infty$$.

Since we just need to show $$S_n$$ tends to infinity, I think a rough estimate should be enough. I think I should consider arbitrarily long sequences of zeroes and ones that follow a particular form and that don't contain six consecutive identical blocks of numbers. Or maybe some recurrence relation involving $$S_n$$ with some base cases might do the trick. Let $$T_n$$ denote the set of binary strings counted by $$S_n$$. Then $$T_i$$ is the set of length i binary strings for $$i < 6.$$ $$T_6$$ only excludes the all zero and all one strings. I think $$T_7$$ just excludes $$\{10^{(6)}, 0^{(6)}1, 0 1^{(6)}, 1^{(6)}0\}$$ since we can only have a block of $$1$$ repeating $$6$$ times consecutively. Obviously for a string of length n, the maximum length of an identical block that repeats at least 6 times consecutively is $$\lfloor \frac{n}6\rfloor$$.

• When does $S_n$ tend to infinity? For what n? Please clarify the question . Jul 2, 2022 at 16:07
• Is $010$ repeated six times an example of six consecutive identical blocks of numbers? Can the block size be one so that $111111$ is six consecutive copies of "$1$"? Jul 2, 2022 at 16:22
• There are only finitely many square free binary words. But A028445 is the sequence of numbers of cube free binary words of length $n$. I believe that the references contain proofs that this sequence grows exponentially, though I have not checked.
– lulu
Jul 2, 2022 at 16:43

Call a binary sequence $$n$$-good if it has both length $$n$$ and the desired property (i.e., it does not contain six consecutive identical blocks of numbers). Call a sequence good if it is $$n$$-good for any natural number $$n$$.

It suffices to show $$S_{n} \geq \frac{3}{2}S_{n - 1}$$ because this would imply $$S_{n} \geq \left(\frac{3}{2}\right)^{n}$$, and the right-hand side diverges. We proceed with induction for which the base case is clear.

Suppose $$\frac{3}{2}S_{i - 1} \leq S_{i}$$ for every index $$i \leq n$$. Combining all $$n$$ inequalities gives $$S_{i} \leq \left(\frac{2}{3}\right)^{n - i}S_{n}$$. Consider the set of all $$n$$-good sequences. We can form $$2S_{n}$$ sequences by taking each $$n$$-good sequence and appending either a $$0$$ or $$1$$ to the end of the sequence.

Among the constructed $$2S_{n}$$ sequences, some will be $$(n + 1)$$-good and others won't be. For the sequences that aren't $$(n + 1)$$-good, you can take some $$(n + 1 - 6x)$$-good sequence and append some block of length $$x$$ exactly $$6$$ times for some $$x \geq 1$$ to construct that sequence. There are $$2^{x}S_{n + 1 - 6x}$$ such sequences. Summing over all possible values of $$x$$, the number of sequences of length $$(n + 1)$$ that are not $$(n + 1)$$-good is at most $$\sum_{k = 1}^{\infty} 2^{k} S_{n + 1 - 6k}$$. However,

$$\sum_{k = 1}^{\infty} 2^{k}S_{n + 1 - 6k} \leq \sum_{k =1}^{\infty} 2^{k} \left(\frac{2}{3}\right)^{6k - 1} S_{n} = \frac{192}{601} S_{n} < \frac{1}{2}S_{n},$$

where the sum of a geometric series formula was used. Taking a complement we see $$S_{n + 1}$$ is at most $$\frac{3}{2}S_{n}$$, and the result follows.

It is shown in [1, Theorem 7] that, on a binary alphabet, cube-free words have an exponential density. This implies that $$S_n$$ tends to infinity.

[1] F.-J. Brandenburg. Uniformly growing $$k$$-th power-free homomorphisms, Theoret. Comput. Sci. 23 (1983), 69–82.

• The question is from an IMO shortlist. I don't think the answer should be too complicated. Jul 10, 2022 at 3:13