Применение производящих функций для получения комбинаторных чисел

Применим теорию производящих функций и получим выражения чисел Фибоначчи. Числа Фибоначчи В_n равны числу способов расположения n знаков, из которых каждый – нуль или единица, в последовательность, не содержащую двух нулей подряд. Эта последовательность задается рекуррентной формулой

(10)

Рассмотрим производящую функцию последовательности чисел Фибоначчи . Умножим рекуррентное уравнение в формуле (10) на t^k и просуммируем полученное выражение от двух до бесконечности. Два числа В₀ и В₁ известны из начальных данных, поэтому необходимо отбросить индексы к=0 и к=1. В результате получим уравнение

или .

Учитывая выражение для производящей функции, получим

Тогда

. (11)

Т.к. обычный степенной ряд, представляющий производящую функцию, есть ряд Тейлора в окрестности точки t=0 , то приведенное выражение можно разложить в ряд Тейлора и получить формулу общего члена B_k. Тогда будем иметь

. (12)