We use the following lemma: there's an infinite sequence $a_1a_2a_3\ldots$ with no block of the form $bbb$, where $b$ is a block (this has appeared before in the forum). If the problem is false, then $S_n<C$ for arbitrarily large $n$ and some constant $C$. Now take a sequence with no $bbb$, and look at its blocks of length $n$ for some large enough $n$ such that $S_n<C$ (in particular $n>4C$, for example). We say that $b_1=a_1 a_2 \ldots a_n, b_2=a_2 a_3 \ldots a_{n+1},$ etc. Obviously, among $b_1, b_2, \ldots, b_{C+1}$ there must be two identical sequences, by pigeonhole. So there are two sequences at most $C$ elements apart. In other words, we have $b_i, b_j$ with $j \leq i+C$, so $a_j=a_i, a_{j+1}=a_{i+1},$ etc. The first part $a_i a_{i+1} \ldots a_j=X$ repeats as long as the two sequences overlap, so the sequence has the form $XX \ldots XR$ where $R$ is of length at most $C$. Since $n$ can be as large as we want, we can get as many $X$'s as we want, in particular at least $3$, which contradicts the fact that our sequence had no block of the form $bbb$. Note that this is much stronger (we have proved $S_n \rightarrow \infty$ for $S_n$ with no three consecutive blocks, instead of $6$).

Note that you can prove by induction that$S_n\geq\ \frac{3}{2}S_{n-1}$,using the recurence:$S_n=2S_{n-1}-\sum 6^kS_{n+1-6k}$

Severius wrote: We use the following lemma: there's an infinite sequence $a_{1}a_{2}a_{3}\ldots$ with no block of the form $bbb$, where $b$ is a block (this has appeared before in the forum). I searched for it and I found nothing. Can you post a link for this lemma?

Denote by $A_n$ the number of sequences with the properties given in the problem. Their number will be $S_n$. It is enough for us to prove that $S_n \geq (\frac{3}{2})^n$, as $\lim_{j \to \infty}i^j= \infty$ when $i>1$. Or in another way said we have to prove the following recursion $S_n \geq \frac{3}{2}S_{n-1}$. We will use induction on $n$ to prove that. It is obvious for $n=1$. Let $S_k \geq \frac{3}{2}S_{k-1}$ for $\forall k=2, 3...n$. Then $S_{n-1} \leq \frac{2}{3}S_n \Rightarrow S_k \leq (\frac{2}{3})^{n-k}$. Let $B_{n+1}$ be the set of all sequences formed up by adding 0 or 1 to a sequence from the set $A_n$. Their number is $2S_n$. These sequences that are not in $A_{n+1}$ will certainly end on six equal consecutive blocks. That is to say their structure will be the following: They will begin with the sequence $A_{n+1-6k}$ for some $k \in \{ 1,2...n \}$ and continue with k-member sequence from 0's and 1's repeated 6 times. Thus for $\forall$ fixed $k \in \{ 1,2...n \}$ the number of sequences with the upper property will be $S_{n+1-6k}.2^k$. Hence the number of sequences in $B_{n+1}$ which won't have the property, given in the problem, won't surpass: $\sum_{k=1}^{n} S_{n+1-6k}.2^k \leq \sum_{k=1}^{n} (\frac{2}{3})^{n-(n+1-6k)}.S_n.2^k \leq S_n \sum_{k=1}^{\infty} (\frac{2}{3})^{6k-1}.2^k= 3. \frac{1}{(\frac{3}{2})^6-2}.S_n < \frac{1}{2}S_n$. Hence $A_{n+1}$ contains at least $2S_n - \frac{1}{2}S_n= \frac{3}{2}S_n$ different sequences that satisfy the problem with which the induction is completed and so the problem is solved.

xirti wrote: Severius wrote: We use the following lemma: there's an infinite sequence $a_{1}a_{2}a_{3}\ldots$ with no block of the form $bbb$, where $b$ is a block (this has appeared before in the forum). I searched for it and I found nothing. Can you post a link for this lemma? Even I did not find it here (though I must say that I never searched for it extensively). But there is something where you can read about it, and this was told to me by my teacher. Such words where a block $b$ doesn't occur more than twice consecutively are called cube free words. Axel Thue's document on cube free words and further extensions of it describe a lot of these things. So on internet you can search for : "Axel Thue cube free words" and hopefully it will show you many results from which you can read more about the topic. Here is an attached document on cube free words on 2 alphabets, and the theorem which is apparently of most interest in the view of this problem is Theorem 3 from the paper

Attachments:
CubeFreeWordsOn2Alphabets.pdf (154kb)