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

Определение

Определение:

Строками Фибоначчи называются строки, удовлетворяющие следующим условиям: [math]F_0 = \epsilon[/math] (пустая строка) [math]F_1 = b[/math] [math]F_2 = a[/math] [math]F_n = F_{n-1}F_{n-2}[/math] (т.е. конкатенации строк [math]F_{n-1}[/math] и [math]F_{n-2}[/math])

Леммы

Лемма:

[math] \exists k : \forall n \geq k \Rightarrow F_{n}^2 [/math] - префикс [math]F_{n+2}[/math]

Доказательство:

[math]\triangleright[/math]

[math] F_{n+2} = F_{n+1}F_{n} = F_{n}F_{n-1}F_{n} = F_{n}F_{n-1}F_{n-1}F_{n-2}[/math][math] = F_{n}F_{n-1}F_{n-2}F_{n-3}F_{n-2} = F_{n}F_{n}F_{n-3}F_{n-2}[/math] Так как мы пользовались формулой [math]F_{n-1} = F_{n-2}F_{n-3}[/math], то рассуждения верны для [math]n \geq 4[/math]. Следовательно, [math]k \geq 6[/math]

[math]\triangleleft[/math]