129
правок
Изменения
м
точки
|about=1
|statement = Для любого целого <tex>n</tex> выполняется <tex>f_nf_{n+1} \neq f_{n+1}f_n</tex>.
|proof = Докажем это утверждение методом математической индукции по <tex>f_n</tex>.
'''База:'''
<tex>f_n=f_{n-1}f_{n-2}=f_{n-2}f_{n-3}f_{n-2}</tex>. Таким образом, <tex>f_{n-2}</tex> является бордером.
Далее, <tex>f_n=f_{n-3}f_{n-3}f_{n-3}f_{n-4}=f_{n-4}f_{n-5}\ldots f_{n-4} </tex>. Получили, что <tex>f_{n-4}</tex> также является бордером.
Продолжая выполнять это преобразование, докажем лемму для всех заданных <tex>i</tex>.
*:Пусть <tex>n \geqslant 2</tex>, тогда <tex>f_n = f_{n-1}f_{n-2}</tex>.
*:Так как <tex>f_{n-1}</tex> и <tex>f_{n-2}</tex> не содержат <tex>x^3</tex>, то такая кратная строка может появиться только на границе строк <tex>f_{n-1}</tex> и <tex>f_{n-2}</tex>.
*:А <tex>f_{n-2}</tex> равно либо <tex>x</tex>, либо <tex>y</tex>, либо начинается с <tex>xy</tex> (при <tex>n \geqslant 4</tex>).
*:Таким образом, достаточно доказать, что последние два символа <tex>f_{n-1}</tex> не равны <tex>xx</tex>.
*:Это выполняется согласно лемме 4, по которой либо <tex>xy</tex>, либо <tex>xyx</tex> является бордером (в зависимости от четности длины строки).
}}
==Обратный морфизм==
\end{array}
\right. </tex>
Здесь <tex>\overline{xx}</tex> обозначает, что после этого вхождения <tex>x</tex> в строке опять следует <tex>x</tex>.
}}
