Изменения
Нет описания правки
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
<!--
==Теорема==
===Вспомогательные леммы и опредления===
Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y \in \Sigma^*</tex>:
*<tex>h(x) = xy</tex>
*<tex>h(y) = x</tex>
Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = b</tex>.
По аналогии можно вычислить <tex>h^*(y) = \{y, x, xy, xyx, \dots\}</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:
{{Определение
|definition=Обобщенная строка Фибоначчи имеет вид <tex>f_n(x,y) = h^n(y)</tex>
}}
Первые несколько обобщенных строк имеют вид:
*<tex>f_0(x,y) = y</tex>
*<tex>f_1(x,y) = x</tex>
*<tex>f_2(x,y)= xy</tex>
*<tex>f_3(x,y)= xyx</tex>
*<tex>f_4(x,y) = xyxxy</tex>
А также в общем случае:
*<tex>f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)</tex>
{{Определение
|definition=Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' как строку, содержащую все строки <tex>f_n(x,y), n \geq 0</tex> в качестве префиксов
}}
Поскольку <tex>h^n(y) = h^{n-k}(h^k(y))</tex>, то <tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y))</tex>, и, так как <tex>h^k(x) = h^{k+1}(y)</tex>, финально получаем:
*<tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.
'''Например''':
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex>
Это равенство походит также и для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \dots</tex>
Так же имеют место быть 2 простые леммы.
{{Лемма
|about = 1
|statement=Для любого целого <tex>n \geq 2</tex> выполняется равенство <tex>f^2_n = f_{n+1}f_{n-2}</tex>
}}
{{Лемма
|about = 2
|statement= Для любого целого <tex>n \geq 3</tex> строка <tex>f_n</tex> имеет грани <tex>f_i</tex> для <tex>i = n-2, n-4,\dots,2-(n\,\,mod \,\,2)</tex>
}}
{{Теорема
|statement=Все строки Фибоначчи <tex>f_n</tex> при <tex>n \geq 7</tex> содержат кубы, но ни одна строка Фибоначчи не содержит кратных подстрок четвертого порядка
|proof=
}}
-->
== См. также ==
[[Слово Туэ-Морса]]
