129
правок
Изменения
Нет описания правки
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geqslant 2</tex>.
|proof=
Докажем методом математической индукции по <tex>f_n</tex>.
'''База:'''
{{Лемма
|about = 4
|statement= Для любого целого <tex>n \geqslant 3</tex> строка <tex>f_n</tex> имеет [[Основные_определения,_связанные_со_строками#border|бордеры]] <tex>f_i</tex> для <tex>i = n-2, n-4,\ldots,2-(n\,\,mod bmod \,\,2)</tex>.
|proof=
Будем последовательно применять лемму 1<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>.
}}
{{Утверждение
|about=2
|statement= В <tex>f_n(x,y)</tex> не может содержаться подстроки <tex>x^3</tex> или <tex>y^2</tex>.
|proof = Докажем для <tex>x^3</tex> методом математической индукции по <tex>f_n</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> является бордером (в зависимости от четности длины строки)
}}
\end{array}
\right. </tex>
Здесь <tex>\overline{abxx}</tex> обозначает, что после этого вхождения <tex>ax</tex> в строке следует <tex>bx</tex>
}}
* [[Слово Туэ-Морса]]
== Источники информации==
* Билл Смит «Методы и алгоритмы вычислений на строках» {{---}} издательство «Вильямс» {{---}} 2006 {{---}} стр. 100-107
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
