129
правок
Изменения
м
Нет описания правки
{{Определение
|definition='''Строками Фибоначчи''' (англ. ''Fibostring'') называются строки над алфавитом <tex>\Sigma = \{ax, by\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:* <tex>h(ax) = abxy</tex> * <tex>h(by) = ax</tex>к строке <tex>s = by</tex>, т.е. последовательность <tex>f_n(x,y) = h^*n(b)</tex>.
}}
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geqslant 2</tex>.
|proof=
Докажем методом математической индукции.по <tex>f_n</tex>
'''База:''' При <tex>n = 2</tex> <tex>f_2=ab=f_1f_0</tex>.
*: При <tex>n = 2</tex> <tex>f_2=ab=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>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, \ldots\}</tex>, и, наконец, определить <tex>n</tex>-ую обобщенную строку Фибоначчи как:{{Определение|definition=Обобщенная строка Фибоначчи (англ. ''generalized Fibostring'') имеет вид <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>
{{Определение
{{Лемма
|about = 2
|statement=Для любого целого <tex>k \geqslant 0</tex> выполняется <tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.|proof= <tex>f_n(x,y) = 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)) = f_{n-k}(h^{k+1}(y),h^k(y))</tex>.
|proof = Докажем это утверждение методом математической индукции.
'''База.''' *:<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_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> было доказано ранее в ходе индукции.
}}
{{Лемма
