Fraenkel word: Difference between revisions

Line 52:

In case 1, by the preceding lemma {{!}}''u''{{!}}'''i''' = {{!}}''u''{{!}}/2''i''+1 and {{!}}''v''{{!}}'''i''' = {{!}}''v''{{!}}/2''i''+1, and hence {{!}}''w''{{!}}'''i''' = {{!}}''w''{{!}}/2''i''+1 = ceil({{!}}''w''{{!}}/2''i''+1).

In case 2, suppose ''w'' = ''ustv'' where ''st'' is as in case 1 and {{!}}''u''{{!}} and {{!}}''v''{{!}} are less than 2''i''+1. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''''i''; ~~hence~~ {{!}}''u''{{!}}<~~sub>'''i''' =~~ {{!}}''st''{{!}}~~'''i'''~~ = {{!}}''st''{{!}}~~/2''i''~~+~~1. As 0 <~~ {{!}}''u''{{!}} + {{!}}''v''{{!}} ≤ 2''i''+1 − 2, we have {{!}}''w''{{!}}'''i''' ≥ ~~ceil(~~{{!}}''w''{{!}}/2<~~sup~~>''i''+1</~~sup~~>~~) − 1~~ = {{!}}''st''{{!}}<~~sub~~>'''i'''</~~sub~~>. On the other hand, {{!}}''w''{{!}}'''i''' < ceil({{!}}''w''{{!}}/2''i''+1), lest ''u'' or ''v'' have an '''i'''. Therefore {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) − 1.

In case 2, suppose ''w'' = ''ustv'' where ''st'' is as in case 1 and {{!}}''u''{{!}} and {{!}}''v''{{!}} are less than 2''i''+1. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''''i''; as {{!}}''st''{{!}} < {{!}}''w''{{!}} = {{!}}''st''{{!}} + {{!}}''u''{{!}} + {{!}}''v''{{!}} ≤ {{!}}''st''{{!}} + 2''i''+1 − 2, we have {{!}}''w''{{!}}'''i''' ≥ {{!}}''st''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) − 1. On the other hand, {{!}}''w''{{!}}'''i''' < ceil({{!}}''w''{{!}}/2''i''+1), lest ''u'' or ''v'' have an '''i'''. Therefore {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) − 1.

}}

@@ Line 52: / Line 52: @@
 In case 1, by the preceding lemma {{!}}''u''{{!}}<sub>'''i'''</sub> = {{!}}''u''{{!}}/2<sup>''i''+1</sup> and {{!}}''v''{{!}}<sub>'''i'''</sub> = {{!}}''v''{{!}}/2<sup>''i''+1</sup>, and hence {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>).
-In case 2, suppose ''w'' = ''ustv'' where ''st'' is as in case 1 and {{!}}''u''{{!}} and {{!}}''v''{{!}} are less than 2<sup>''i''+1</sup>. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>; hence {{!}}''u''{{!}}<sub>'''i'''</sub> = {{!}}''st''{{!}}<sub>'''i'''</sub> = {{!}}''st''{{!}}/2<sup>''i''+1</sup>. As 0 < {{!}}''u''{{!}} + {{!}}''v''{{!}} &le; 2<sup>''i''+1</sup> &minus; 2, we have {{!}}''w''{{!}}<sub>'''i'''</sub> &ge; ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1 = {{!}}''st''{{!}}<sub>'''i'''</sub>. On the other hand, {{!}}''w''{{!}}<sub>'''i'''</sub> < ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>), lest ''u'' or ''v'' have an '''i'''. Therefore {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1.
+In case 2, suppose ''w'' = ''ustv'' where ''st'' is as in case 1 and {{!}}''u''{{!}} and {{!}}''v''{{!}} are less than 2<sup>''i''+1</sup>. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>; as {{!}}''st''{{!}} < {{!}}''w''{{!}} = {{!}}''st''{{!}} + {{!}}''u''{{!}} + {{!}}''v''{{!}} &le; {{!}}''st''{{!}} +  2<sup>''i''+1</sup> &minus; 2, we have {{!}}''w''{{!}}<sub>'''i'''</sub> &ge; {{!}}''st''{{!}}<sub>'''i'''</sub> =  ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1. On the other hand, {{!}}''w''{{!}}<sub>'''i'''</sub> < ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>), lest ''u'' or ''v'' have an '''i'''. Therefore {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1.
 }}