Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From here.

This particular item deals with excluding strings that have a consecutive repeated sequence. That is, ab*b*a and abcab*ab*c both have doubles whereas abcabacba doesn't. When working in base $2$, the number of sequences is easily seen to be finite.

0
1

00
01
10
11

010
011
100
101

0100
0101
1010
1011

They also mention that base $10$ is known to be infinite. In addition, base $3$ seems to be infinite, as evidenced by this exponentially-growing pattern.

My question is: how can you prove that the number of repetition-free sequences is infinite for base $b \ge 3$?

share|improve this question
2  
If you can prove it is infinite for base $b$, then it is infinite for any base $b'\geq b$. Now look up Thue's sequence. (It may be called something else, but Thue gave an infinite squarefree word in three letters). –  Arturo Magidin Feb 14 '12 at 6:23
    
P.S. The more common term is "squarefree words", not "repetition-less digit strings". That might also help with internet searches. –  Arturo Magidin Feb 14 '12 at 6:26
    
You mean the Thue-Morse sequence? But that's in binary... –  El'endia Starman Feb 14 '12 at 6:26
1  
No, I mean the sequence that Thue produced for an alphabet with three letters. E.g., Wikipedia's entry on "Squarefree word". –  Arturo Magidin Feb 14 '12 at 6:28
    
Arturo means what Arturo says. –  Gerry Myerson Feb 14 '12 at 6:28

2 Answers 2

up vote 6 down vote accepted

This paper gives a very nice elementary presentation of the Thue-Morse sequence and in particular of the result that there is an infinite square-free sequence over an alphabet of three letters.

share|improve this answer

Thue proved that any alphabet on three or more letters contains an infinite squarefree word. An example due to Leech (A problem on strings of beads, Math. Gazette 41 (1957) 277– 278):

On the alphabet that contains $a$, $b$, and $c$, define $w_1$ to be a word beginning with $a$ (say, $w_1=a$).

Given $w_n$, define $w_{n+1}$ by replacing each occurrence of $a$ in $w_n$ by $abcbacbcabcba$; every occurrence of $b$ in $w_n$ by $bcacbacabcacb$; and every occurrence of $c$ by $cabacbabcabac$.

Then $w_n$ converges to an infinite squarefree word, which begins $$abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb\ldots$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.