Задача “Двоичные числа” (Рекуррентное соотношение с одним параметром )

Условие задачи: ссылка
Основная идея: Чтобы прочувствовать решение задачи предлагаю начать с более простого случая, когда K=2. Обозначим K(n) – количество n битных чисел без 2-ых подряд идущих единиц. K(1) = 2 – факт очевидный. Найдем решение для n=2. На вторую позицию можно поставить либо ноль, либо единицу. Ноль можно ставить смело, а вот единица может образовать запрещенную комбинацию, если на первой позиции также стояла единица. Проанализируем таблицу:

комбинация	количество
*0	K(1)
01	1
11	0

Делаем вывод, что K(2) = K(1) + 1. Двигаемся дальше. По такой же схеме получают таблицу для n=3

комбинация	количество
**0	K(2)
*01	K(1)
*11	0

K(3) = K(2)+K(1). Придерживаясь этой логики получаем универсальную формулу K(n) = K(n-1) + K(n-2). Если обозначить K(0) = 1, то терминальное условие для K(2) можно отдельно не прописывать.
Двигаемся дальше. Рассмотрим решение первоначальной задачи для K=3. Ход рассуждений не меняется. На первую позицию смело ставим ноль и единицу, значит K(1) = 2, на вторую позицию можно также смело ставить и ноль и единицу, т.е. запрещенная комбинация из 3 подряд единиц не может быть достигнута на текущем шаге , значит K(2) = K(1) + K(1) = 2K(1)=4. Первое слагаемое – это количество решений, если поставим на вторую позицию ноль, второе слагаемое – если поставим единицу. Как быть если n = 3 и k=3? Очевидно, что запрещенная комбинация может быть только одна. Общее количество всех комбинаций будет 8, следовательно K(3) = 2K(2)-1. Мы пришли к самому интересному: n=4, k=3. Рисуем таблицу

комбинация	количество
***0	K(3)
**01	K(2)
**11	0
*011	K(1)
*111	0

Поясню, почему в комбинации “**11” стоит 0. Эта комбинация является общим случаем комбинаций “*011” и “*111”, которые рассмотрены в таблице.
Получили K(4) = K(3)+K(2)+K(1). Для общего случая имеем K(n)=сумма K(i) для i из [n-k,n-1] (Когда прикручу Tex, формулы обретут свои заслуженные очертания). Не забываем про терминальные условия: если i<n, то K(i) = 2^i; если i=1, то K(i) = 2^i-1. Во всех остальных случаях работает наша формула.
Исходный код:  здесь