Соотношениями

Связь производящих функций с линейными рекуррентными

Пусть имеем дробно-рациональную функцию

f(x) = = ,

которая разлагается в ряд f₀ + f₁x + f₂ x + …. Отсюда A(x) = B(x)×f(x). Подставим вместо f(х) ее ряд – получим систему уравнений:

b₀ f₀ = a₀;

b₀ f₁ + b₁ f₀ = a₁;

b₀ f₂ + b₁ f₁ + b₂ f₀ = a₂;

………………………..

b₀ f_{m –1} + b₁ f_{m –2} +… + b_{m –1} f₀ = a_{m – 1};

b₀ f_m + b₁ f_{m –1} +… + b_m f₀ = 0;

………………………………..

b₀ f_{m + n} + b₁ f_{m –1 + n} +… + b_m f_n = 0;

……………………………

Во всех уравнениях, начиная с m+1-го, правая часть равна 0, т.к. a_{m + 1} = … = a_{m + n} =…= 0. Следовательно, имеем линейное рекуррентное соотношение

b₀ f_{m + n} + b₁ f_{m –1 + n} +… + b_m f_n = 0, (3.13)

которому удовлетворяют члены ряда для функции f(x). Таким образом, мы получили теорему о связи производящих функций с линейными рекуррентными соотношениями:

Теорема 3.5. Для того, чтобы производящая функция числовой последовательности была правильной рациональной дробью необходимо и достаточно, чтобы члены этой последовательности удовлетворяли линейному рекуррентному соотношению, характеристическое уравнение которого совпадает со знаменателем этой дроби, записанным в обратном порядке.

Пример 3.10. Найдем производящую функцию для чисел Фибоначчи.

Решение. Имеем рекуррентное соотношение: F_n+2 – F _n+1– F_n = 0. Следовательно, f(x) = . A и В легко найти с помощью деления многочленов:

Следовательно, 0 = F₀ = B; 1 = F₁ = A + B, т.е. В = 0; А = 1 или .