Задача
COM-B1-M10-P003 Строки длины \(4\)
#3
★☆☆☆☆ Уровень 1 из 5
Сколько двоичных строк длины \(4\) не содержат двух соседних единиц?
Разделите по последнему символу.
Пусть \(a_n\) - число таких строк. Тогда \(a_0=1\), \(a_1=2\), \(a_n=a_{n-1}+a_{n-2}\). Получаем \(a_2=3\), \(a_3=5\), \(a_4=8\).
Важно не путать с лестницей: начальные условия другие.