Рекуррентные соотношения - часть 3
Иными словами,
- целая часть числа
(в дальнейшем будем обозначать целую часть числа
через
; таким образом,
).
В самом деле,
- это число всех
- последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно
единиц и
нулей, равно
. Так как при этом должно выполняться неравенство
, то
изменяется от 0 до
. Применяя правило суммы, приходим к соотношению (7.3).
Равенство (7.3) можно доказать и иначе. Положим
где
. Из равенства
легко следует, что
Кроме того, ясно, что
и
. Так как обе последовательности
и
удовлетворяют рекуррентному соотношению
, то имеем
и, вообще,
.
Содержание Назад Вперед