Fraenkel word: Difference between revisions

Line 22:

The theorem will be a consequence of the following lemmas:

{{theorem|name=Lemma|contents=Let ''F''''n'' denote the non-circular Fraenkel word on ''n'' letters. For ''n'' ≥ 1 and 0 ≤ ''i'' ≤ ''n'' − 1, the letter '''i''' appears every 2''i''+1 letters in ''F''''n''; i.e. in every subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2''i''+1 − 1.}}

{{theorem|name=Lemma|contents=Let ''F''''n'' denote the non-circular Fraenkel word on ''n'' letters. For ''n'' ≥ 1 and 0 ≤ ''i'' ≤ ''n'' − 1, the letter '''i''' appears once every 2''i''+1 letters in ''F''''n''; i.e. in every subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2''i''+1 − 1.}}

{{proof|contents=We prove this by induction on ''n''. The ''n'' = 1 case being trivial, for ''n'' > 1 we start by observing that '''i''' always occurs as the greatest letter of a subword that is the Fraenkel word ''F''''i''+1, and ''F''''i''+1 is always flanked by letters that are greater. This subword '''i'''''F''''i'' is not a suffix of ''F''''n'', and we thus have

@@ Line 22: / Line 22: @@
 The theorem will be a consequence of the following lemmas:
-{{theorem|name=Lemma|contents=Let ''F''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For ''n'' &ge; 1 and 0 &le; ''i'' &le; ''n'' &minus; 1, the letter '''i''' appears every 2<sup>''i''+1</sup> letters in ''F''<sub>''n''</sub>; i.e. in every subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2<sup>''i''+1</sup> &minus; 1.}}
+{{theorem|name=Lemma|contents=Let ''F''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For ''n'' &ge; 1 and 0 &le; ''i'' &le; ''n'' &minus; 1, the letter '''i''' appears once every 2<sup>''i''+1</sup> letters in ''F''<sub>''n''</sub>; i.e. in every subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2<sup>''i''+1</sup> &minus; 1.}}
 {{proof|contents=We prove this by induction on ''n''. The ''n'' = 1 case being trivial, for ''n'' > 1 we start by observing that '''i''' always occurs as the greatest letter of a subword that is the Fraenkel word ''F''<sub>''i''+1</sub>, and ''F''<sub>''i''+1</sub> is always flanked by letters that are greater. This subword  '''i'''''F''<sub>''i''</sub> is not a suffix of ''F''<sub>''n''</sub>, and we thus have