Сколько существует натуральных чисел, не больших 1023, бинарная запись которых не содержит трех одинаковых бит подряд?
Я рассуждала так:
Пусть

- количество n - битных чисел, удовлетворяющих условию задачи.
Предположим, мы уже имеем n - битное число, удовлетворяющее условию задачи. Добавим ещё один бит.
Если добавляемый бит не равен последнему биту, его всегда можно добавить - имеем количество вариантов, равное

. Если же равен, значит не должны быть равны биты n и

. Стало быть,

. То бишь мы получаем последовательность Фибоначчи, и тогда ответ на задачу будет 231. Но правильный ответ, почему-то, оказался 228.