Fraenkel word: Difference between revisions
| Line 19: | Line 19: | ||
To prove this, we prove the following lemmas by induction on ''n'': | To prove this, we prove the following lemmas by induction on ''n'': | ||
{{theorem|name=Lemma|contents=Let ''G''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For all ''n'' ≥ 1, 0 ≤ ''i'' ≤ ''n'' − 1, and 1 ≤ {{!}}''w''{{!}} ≤ 2<sup>''n''/2</sup> − 2, the following holds for any | {{theorem|name=Lemma|contents=Let ''G''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For all ''n'' ≥ 1, 0 ≤ ''i'' ≤ ''n'' − 1, and 1 ≤ {{!}}''w''{{!}} ≤ 2<sup>''n''/2</sup> − 2, the following holds for any subword ''w'' of ''G''<sub>''n''</sub>: | ||
# If {{!}}''w''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup> | # If {{!}}''w''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup> | ||
# If {{!}}''w''{{!}} ≢ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = either floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>). | # If {{!}}''w''{{!}} ≢ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = either floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>). | ||