Слово Фибоначчи

2012-03-27T13:40:04Z

78.37.210.205:

==Определение==
{{Определение
|definition=Морфизмом называется отображение <tex>h</tex>, которое каждоый букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>. отображение <tex>h</tex> также распространяется на любую строку <tex>x</tex> из множества <tex>A^{+}</tex> путем использования следующего тождества: 
<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex>. 
Для полноты распространим отбражение на множество <tex>A^{*}</tex>, положив, что для любого морфизма <tex>h(\epsilon) = \epsilon</tex>.
}}

Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: 
<tex>h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}</tex>. 
где <tex>h^0(x_0) = x_0</tex> и для любого целого <tex>k \geq 1 h^k(x_0) = h(h^{k-1}(x_0))</tex>. 
Например: 
<tex>A = \{a,b\}, h(a) = a, h(b) = ab</tex>. 
<tex>h^*(a) = \{a,a,...\}</tex> 
<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex> 

{{Определение
|definition=Строки Фибоначчи - строки, порожденные следующим морфизмом:
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>
}}
==Свойства==
Введем множество <tex>h(f_0) = \{f_0, f_1,f_2,...\}</tex>, где <tex>f_n = h(f_{n-1})</tex> для любого целого <tex>n \geq 1</tex>, а <tex>f_0 = b</tex>. 
Первые несколько строк Фибоначчи: 
* <tex>f_0 = b</tex>
* <tex>f_1 = a</tex>
* <tex>f_2 = ab</tex>
* <tex>f_3 = aba</tex>
* <tex>f_4 = abaab</tex>
* <tex>f_5 = abaababa</tex>

==Леммы==
{{Лемма
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_n-1 + f_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>
}}

Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.

Викиконспекты - Вклад участника [ru]

Слово Фибоначчи