'''База:'''
*: При <tex>n = 2</tex> выполняется <tex>f_2=xy=f_1f_0</tex>.
'''Переход:'''
*:Пусть <tex>n > 2</tex> и <tex>f_n = f_{n-1}f_{n-2}</tex>. *:<tex>f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})</tex>. *:Так как отображение <tex>h</tex> {{---}} линейно (т.е. <tex>h(xy) = h(x)h(y)</tex>), то можно продолжить равенство:*:<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>.
}}
'''База:'''
*:<tex>f_0f_1 \neq f_1f_0</tex>
'''Переход:'''
*:<tex>f_nf_{n+1}=f_nf_nf_{n-1}=f_nf_{n-1}f_{n-2}f_{n-1}</tex>*:<tex>f_{n+1}f_n=f_nf_{n-1}f_n=f_nf_{n-1}f_{n-1}f_{n-2}</tex>*:Но то, что <tex> f_{n-2}f_{n-1} \neq f_{n-1}f_{n-2} </tex> было доказано ранее в ходе индукции.
}}
{{Лемма
'''База:'''
*:<tex>f_0=y,f_1=x</tex> не содержат <tex>x^3</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> является бордером (в зависимости от четности длины строки).
}}
==Обратный морфизм==
'''Пример''':
*: <tex>f_4=xyxxy</tex>. *: Будем последовательно применять морфизм:*: Префикс <tex>xy</tex> переходит в <tex>x</tex>, центральный <tex>x</tex> переходит в <tex>y</tex>, а суффикс <tex>xy</tex> также переходит в <tex>x</tex>.*: Получили <tex>xyx = f_3</tex>.
== Связь с задачей о построении исключений==
{{Утверждение
