числа-фибоначчи - Последовательности

В этой задаче ответом числа Фибоначчи и являются. То, что написано у Вас -- это они самые, уменьшенные на единицу. Разница в ответе вызвана, вероятно, тем, что Вы последовательность из одних нулей не учитываете, но удобнее было бы учитывать.

Количество двухразрядных чисел без соседних единиц получается равно трём: $%00$%, $%01$%, $%10$%. То есть $%f(2)=3$%, где $%f(n)$% означает количество $%n$%-разрядных чисел без соседних единиц.

Рекуррентную формулу, задающую числа Фибоначчи, то есть $%f(n)=f(n-1)+f(n-2)$% (при $%n\ge2$%), где $%f(0)=1$%, $%f(1)=2$%, для таких чисел доказать легко. Составим полный каталог $%n$%-разрядных чисел. Среди них есть те, которые оканчиваются на $%0$%, и те, которые оканчиваются на $%1$%. Подсчитаем отдельно то и другое.

Сколько чисел оканчивается на $%0$%? Если этот ноль справа удалить, то мы получим полный каталог $%(n-1)$%-разрядных чисел -- так как $%0$% справа приписать можно всегда. То есть таких чисел с нулём на конце у нас $%f(n-1)$%. А сколько оканчивается на $%1$%? Если мы сотрём $%1$% справа, то получим полный список $%(n-1)$%-разрядных чисел, оканчивающихся на $%0$%, так как $%1$% могла быть приписана только к нулю. И теперь, если мы удалим ещё и этот ноль справа, то перед нами будет весь список $%(n-2)$%-разрядных чисел. Итого на $%1$% оканчивается $%f(n-2)$% числа. Складывая то и другое, получаем требуемую формулу.

Можно при небольших значениях $%n$% создать такие списки, и описанная закономерность сразу себя обнаружит.