Изменения

Введем множество <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>.<br>Первые несколько строк Фибоначчи: <br>* <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> \exists k : \forall f_n = f_n-1 + f_n-2, n \geq k \Rightarrow F_{n}^2 </tex> - префикс <tex>F_{n+2}</tex> .|proof=Доказательство нетрудно получить методом математической индукции.

|proofБаза. При <tex>n =2</tex> равенство очевидно. Переход. Пусть <tex> F_{n+2} = F_{n+1}F_{n} f_n = F_{n}F_f_{n-1}F_{n} = F_{n}F_{n-1}F_{n-1}F_+ f_{n-2}</tex>. <tex> = F_f_{n+1}F_= h(f_n) = h(f_{n-1}F_+ f_{n-2}F_{n)</tex>. Т.к. h -3}F_{n-2} линейна (т.е. <tex>h(x+y) = F_{n}F_{n}F_{n-3}F_{n-2}h(x) + h(y)</tex> ), то можно продолжить равенство.Так как мы пользовались формулой <tex>F_f_{n+1} = h(f_{n-1} = F_) + h(f_{n-2}F_) = f_{n} + f_{n-31}</tex>, то рассуждения верны для <tex>n \geq 4</tex>. Следовательно, <tex>k \geq 6</tex>