Изменения
Нет описания правки
{{Определение
|definition='''Строками Фибоначчи''' являются строки, порожденные следующим морфизмом:полученные последовательным применением морфизма <tex>h</tex> к строке <tex>x_0 = b</tex>, т.е. <tex>h^*(b)</tex>.
* <tex>A = \{a,b\}</tex>
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>
}}
Первые несколько строк Фибоначчи: <br>
* <tex>f_0 = b</tex>
==Леммы==
{{Лемма
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_nf_{n-1 } + f_nf_{n-2}, n \geq 2</tex>.
|proof=
Доказательство нетрудно получить методом математической индукции.
База. При <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>. Т.к. h {{- --}} линейна (т.е. <tex>h(x+y) = h(x) + h(y)</tex>), то можно продолжить равенство.
<tex>f_{n+1} = h(f_{n-1}) + h(f_{n-2}) = f_{n} + f_{n-1}</tex>
}}
