Fraenkel word: Difference between revisions

Line 28:

<math> w = u(\mathbf{1}^\prime, \mathbf{2}^\prime, ..., \mathbf{(n-1)}^\prime),</math>

where ''u'' is a subword of ''G''''n''− 1 with 1 ≤ {{!}}''u''{{!}} ≤ 2''n''−1 − 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}'''0''' = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2''i'', by the inductive hypothesis applied to subwords of ''F''''n''−1 we have {{!}}''w''{{!}}/2''i''+1 = {{!}}''u''{{!}}/2''i'' = {{!}}''u''{{!}}'''i−1''' = {{!}}''w''{{!}}'''i''' for 1 ≤ ''i'' ≤ ''n'' − 1, as desired.

where ''u'' is a subword of ''G''''n''− 1 with 1 ≤ {{!}}''u''{{!}} ≤ 2''n''−1 − 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}'''0''' = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2''i'', by the inductive hypothesis applied to subwords of ''G''''n''−1 we have {{!}}''w''{{!}}/2''i''+1 = {{!}}''u''{{!}}/2''i'' = {{!}}''u''{{!}}'''i−1''' = {{!}}''w''{{!}}'''i''' for 1 ≤ ''i'' ≤ ''n'' − 1, as desired.

In the second case, if {{!}}''w''{{!}} is odd, If {{!}}''w''{{!}} is even, we treat ''w'' as a word formed with consecutive length-2 subwords for letters, working in the next lower non-circular Fraenkel word, recursively until we reach a word ''v'' of odd length, say in ''G''''n''−''r''. By the inductive hypothesis, ''v'' satisfies {{!}}''v''{{!}}'''j''' = floor({{!}}''v''{{!}}/2''j''+1) or ceil({{!}}''v''{{!}}/2''j''+1) for all ''j'', 0 ≤ j ≤ n − r − 1. This implies that {{!}}''u''{{!}}'''j+r''' = floor({{!}}''u''{{!}}/2''j''+''r''+1) or ceil({{!}}''u''{{!}}/2''j''+''r''+1). For 1 ≤ ''s'' < ''r'', we can apply the first case of the inductive hypothesis to the subword ''v''''s'' corresponding to ''u'' in ''G''''n''−''s'', obtaining {{!}}''v''''s''{{!}}'''0''' = {{!}}''v''''s''{{!}}/2 and hence after substituting back, {{!}}''w''{{!}}'''s''' = {{!}}''w''{{!}}/2''s''+1.}}

@@ Line 28: / Line 28: @@
 <math> w = u(\mathbf{1}^\prime, \mathbf{2}^\prime, ..., \mathbf{(n-1)}^\prime),</math>
-where ''u'' is a subword of ''G''<sub>''n''&minus; 1</sub> with 1 &le; {{!}}''u''{{!}} &le; 2<sup>''n''&minus;1</sup> &minus; 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}<sub>'''0'''</sub> = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2<sup>''i''</sup>, by the inductive hypothesis applied to subwords of ''F''<sub>''n''&minus;1</sub> we have {{!}}''w''{{!}}/2<sup>''i''+1</sup> = {{!}}''u''{{!}}/2<sup>''i''</sup> = {{!}}''u''{{!}}<sub>'''i&minus;1'''</sub> = {{!}}''w''{{!}}<sub>'''i'''</sub> for 1 &le; ''i'' &le; ''n'' &minus; 1, as desired.
+where ''u'' is a subword of ''G''<sub>''n''&minus; 1</sub> with 1 &le; {{!}}''u''{{!}} &le; 2<sup>''n''&minus;1</sup> &minus; 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}<sub>'''0'''</sub> = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2<sup>''i''</sup>, by the inductive hypothesis applied to subwords of ''G''<sub>''n''&minus;1</sub> we have {{!}}''w''{{!}}/2<sup>''i''+1</sup> = {{!}}''u''{{!}}/2<sup>''i''</sup> = {{!}}''u''{{!}}<sub>'''i&minus;1'''</sub> = {{!}}''w''{{!}}<sub>'''i'''</sub> for 1 &le; ''i'' &le; ''n'' &minus; 1, as desired.
 In the second case, if {{!}}''w''{{!}} is odd, If {{!}}''w''{{!}} is even, we treat ''w'' as a word formed with consecutive length-2 subwords for letters, working in the next lower non-circular Fraenkel word, recursively until we reach a word ''v'' of odd length, say in ''G''<sub>''n''&minus;''r''</sub>. By the inductive hypothesis, ''v'' satisfies {{!}}''v''{{!}}<sub>'''j'''</sub> = floor({{!}}''v''{{!}}/2<sup>''j''+1</sup>) or ceil({{!}}''v''{{!}}/2<sup>''j''+1</sup>) for all ''j'', 0 &le; j &le; n &minus; r &minus; 1. This implies that {{!}}''u''{{!}}<sub>'''j+r'''</sub> =  floor({{!}}''u''{{!}}/2<sup>''j''+''r''+1</sup>) or ceil({{!}}''u''{{!}}/2<sup>''j''+''r''+1</sup>). For 1 &le; ''s'' < ''r'', we can apply the first case of the inductive hypothesis to the subword ''v''<sub>''s''</sub> corresponding to ''u'' in ''G''<sub>''n''&minus;''s''</sub>, obtaining {{!}}''v''<sub>''s''</sub>{{!}}<sub>'''0'''</sub> = {{!}}''v''<sub>''s''</sub>{{!}}/2 and hence after substituting back, {{!}}''w''{{!}}<sub>'''s'''</sub> = {{!}}''w''{{!}}/2<sup>''s''+1</sup>.}}