Задача
COM-B1-M10-P022 Формула для строк
#22
★★★★☆ Уровень 4 из 5
Докажите, что число двоичных строк длины \(n\) без двух соседних единиц равно \(F_{n+2}\), если \(F_1=1\), \(F_2=1\).
Сравните начальные значения и рекурсию.
Пусть \(a_n\) - число таких строк. Как обычно, \(a_n=a_{n-1}+a_{n-2}\): строка заканчивается на \(0\) или на \(01\). Начальные значения \(a_0=1\), \(a_1=2\). Для чисел Фибоначчи \(F_{2}=1\), \(F_{3}=2\). Значит \(a_0=F_2\), \(a_1=F_3\), и обе последовательности удовлетворяют одной рекурсии. Следовательно, \(a_n=F_{n+2}\).
Аккуратная работа с индексами.