В предыдущем разделе непосредственно установлена связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно установить и иначе, непосредственно доказав, что число
решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению
(7.5)
что и числа Фибоначчи. В самом деле, возьмем любую
-последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим
-последовательность, удовлетворяющую нашему условию. Если взять любую
- последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим
-последовательность с тем же свойством. Таким образом доказано, что число последовательностей, оканчивающихся на нуль, равно
.
Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1
-последовательность может быть любой, лишь бы в ней не шли подряд две единицы. Поэтому число последовательностей, оканчивающихся единицей, равно
. Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что
.
Таким образом, получено то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа
