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

Материал из Викиконспекты
Перейти к: навигация, поиск

Определение

Определение:
Строками Фибоначчи называются строки, удовлетворяющие следующим условиям:
  • [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]