40
правок
Изменения
Произведение Адамара, Начало
==Теорема==
{{Теорема
|statement= Произведение Адамара двух рациональных производящих функций рационально.}}
Для доказательства этой теоремы нам понадобится новая характеризация рациональных производящих функций.
{{Лемма
|statement= Производящая функция для последовательности <tex>a_0, a_1,
a_2, \dots</tex> рациональна тогда и только тогда, когда существуют такие числа <tex>q_1, \dots, q_l</tex> и такие многочлены <tex>p_1(n),
\dots, p_l(n)</tex>, что начиная с некоторого номера <tex>n</tex>
<tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>
Выражение в правой части равенства называется квазимногочленом от переменной <tex>n</tex>.}}===Доказательство==|proof=
<tex>\Rightarrow</tex>
<tex>\Leftarrow</tex>
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена <tex>p(n) q^{n}</tex> соответствующая производящая функция рациональна. Пусть степень многочлена <tex>p</tex> равна <tex>k - 1</tex>. Многочлены <tex>P_0, P_1, \dots, P_{k - 1}</tex>, определенные равенством <tex>\frac{(n + 1)(n + 2.11PRAVKAAAA)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}</tex>, образуют базис в пространстве многочленов степени не выше <tex> k - 1</tex>. Действительно, любая последовательность многочленов степеней <tex>0, 1, \dots, k - 1</tex> образует базис в этом пространстве. Поэтому многочлен <tex>p</tex> представляется в виде линейной комбинации многочленов <tex>P_i</tex> и соответствующая производящая функция есть просто линейная комбинация функций <tex>(1 - q s)^{-j}</tex>, <tex>j = 0, 1, \dots, k - 1</tex>.Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных <tex>q_i</tex>.Лемма доказана.}} ===Доказательство теоремы===Для завершения доказательства теоремы осталось заменить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>
