5
правок
Изменения
Добавлен знак умножения
С помощью производящих функций можно доказывать различные утверждения о свойствах последовательностей и сумм. Обычно если нужно доказать равенство двух выражений <tex>expr^1_n</tex> и <tex>expr^2_n</tex>, нужно найти производящую функцию последовательности <tex>\{expr^1\}_{n = 1}^{\infty}</tex> и последовательности <tex>\{expr^2\}_{n = 1}^{\infty}</tex> и проверить, что эти производящие функции совпадают. Продемонстрируем применение этого принципа на примерах:
В дальнейшем будем обозначать <tex>[x^n]A(x)</tex> коэффициент при <tex>x^n</tex> в формальном степенном ряде <tex>A(x)</tex>
== Пример № 1 ==
{{Задача
<tex>[x^{2k + 1}]C(x) = \sum\limits_{i = 0}^{2k + 1}((i + 1) \cdot (-1)^{2k + 1 - i} \cdot (2k + 2 - i))</tex>
Рассмотрим <tex>i</tex>-ое и <tex>2k + 1 - i</tex>-ое слагаемые этой суммы равны. Модуль <tex>i</tex>-ого равен <tex>(i + 1) \cdot (2k + 2 - i)</tex>, а модуль <tex>2k + 1 - i</tex>-ого слагаемого равен <tex>(2k + 1 - i + 1) \cdot (2k + 2 - (2k + 1 - i)) = (2k + 2 - i) \cdot (i + 1)</tex>, то есть слагаемые равны по модулюабсолютной величине. Знак <tex>i</tex>-ого слагаемого определяется выражением <tex>(-1)^{2k + 1 - i} = (-1)^{1 - i}</tex>, а знак <tex>2k + 1 - i</tex>-ого {{---}} выражением <tex>(-1)^{2k + 1 - (2k + 1 - i)} = (-1)^i</tex>, то есть эти слагаемые равны по модулю, но противоположны по знаку.
Так как слагаемых всего <tex>2k + 1 - 0 + 1</tex> (то есть их чётное число), и каждое слагаемое входит в сумму дважды с противоположными знаками, <tex>[x^{2k + 1}]C(x) = 0 ~~~~ \textbf{(1)}</tex>
<tex>[x^{2k}]C(x) = \sum\limits_{i = 0}^{2k}(i + 1) \cdot (-1)^{2k - i} \cdot (2k + 1 - i) = \sum\limits_{i = 0}^{2k}(i + 1) \cdot (-1)^i \cdot (2k + 1 - i) ~~~~ \textbf{(2)}</tex>
Учитывая <tex>\textbf{(1)}</tex> и <tex>\textbf{(12)}</tex>, получаем, что
<tex>C(x) = \sum\limits_{n = 0}^{\infty}x^{2n} \cdot \sum\limits_{k = 0}^{2n}(k + 1) \cdot (-1)^k \cdot (2n + 1 - k)</tex>
Тогда <tex>\sum\limits_{k = 0}^{2n} (-1)^k \cdot (k + 1) \cdot (2n + 1 - k) = n + 1</tex>
== Пример № 2 ==
{{Лемма
|id=lemma1
|statement=Пусть последовательность <tex>a_0, a_1, a_2, \ldots, a_n \ldots</tex> порождается производящей функцией <tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \sum\limits_{n = 0}^{\infty}a_n \cdot t^n</tex>. Тогда последовательность <tex>a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i = 0}^{n}a_i, \ldots</tex> порождается производящей функцией <tex>\dfrac{A(t)}{1 - t} = \dfrac{\sum\limits_{n = 0}^{\infty}a_n \cdot t^n}{1 - t}</tex>
|proof= По определению [[Арифметические действия с формальными степенными рядами#div | деления формальных степенных рядов]], известноИзвестно, что <tex>\dfrac{1}{1 - t} = \sum\limits_{n = 0}^{\infty}t^n</tex>
Рассмотрим производящую функцию <tex>\dfrac{A(t)}{1 - t} = A(t) \cdot \dfrac{1}{1 - t} = (\sum\limits_{n = 0}^{\infty}a_n \cdot t^n) \cdot (\sum\limits_{n = 0}^{\infty}1 \cdot t^n) = \sum\limits_{n = 0}^{\infty}t^n \cdot (\sum\limits_{k = 0}^{n} a_k \cdot 1) = \sum\limits_{n = 0}^{\infty}t^n \cdot (\sum\limits_{k = 0}^{n} a_k)</tex>
То есть <tex>[t^n]\dfrac{A(t)}{1 - t} = \sum\limits_{k = 0}^{n} a_k</tex>, то есть <tex>\dfrac{A(t)}{1 - t}</tex> является производящей функцией последовательности <tex>a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{k = 0}^{n}a_k, \ldots</tex>
}}
{{Определение
|id=fib.
|definition='''Числа Фибоначчи''' {{---}} последовательность чисел, задаваемая рекурентным соотношением <tex>f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}</tex>, для <tex>n \geqslant 2</tex>.
}}
{{Задача
|definition = Доказать, что <tex>f_0 + f_1 + f_2 + \ldots + f_n = f_{n + 2} - 1</tex>, где <tex>f_n</tex> {{---}} <tex>n</tex>-ое число Числа Фибоначчи
}}
<tex> = \dfrac{2 + t}{1 - t - t^2} - \dfrac{1}{1 - t} = \dfrac{(2 + t) \cdot (1 - t) - 1 \cdot (1 - t - t^2)}{(1 - t - t^2) \cdot (1 - t)} = \dfrac{2 - 2t + t -t^2 - 1 + t + t^2}{(1 - t - t^2) \cdot (1 - t)} = \dfrac{1}{(1 - t - t^2) \cdot (1 - t)}</tex>
Тогда <tex>A(t) = B(t)</tex>, то есть производящие функции последовательностей <tex>f_0, f_0 + f_1, f_0 + f_1 + f_2, \ldots, \sum\limits_{k = 0}^{n} f_k, \ldots</tex> и <tex>f_2 - 1, f_3 - 1, \ldots, f_{n + 2} - 1, \ldots</tex> совпадают, а значит, совпадают и эти последовательности. Поэтому <tex>f_0 + f_1 + f_2 + \ldots + f_n = f_{n + 2} - 1</tex> == Пример № 3 == {{Задача|definition = Доказать, что <tex>f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_n \cdot f_{n+1}</tex>.}}[[Решение рекуррентных соотношений#.5Bmath.5D3.5B.2Fmath.5D_.D0.BF.D1.80.D0.B8.D0.BC.D0.B5.D1.80 | Известно]], что производящая функция последовательности <tex>f_0^2, f_1^2, \ldots, f_n^2, \ldots</tex> равна <tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex> Используя [[Использование производящих функций для доказательства тождеств#lemma1 | лемму]] из примера <tex>2</tex>, найдём производящую функцию для последовательности <tex>f_0^2, f_0^2 + f_1^2, f_0^2 + f_1^2 + f_2^2, \ldots</tex>:<br><tex>A(z) = \dfrac{1 - z}{(1 - 2z - 2z^2 + z^3)(1 - z)} = \dfrac{1}{1 - 2z - 2z^2 + z^3}.</tex><br> Теперь получим производящую функцию <tex>B(z)</tex> для последовательности, соответствующей правой части <tex>(f_0 \cdot f_1, f_1 \cdot f_2, \ldots )</tex>:<br><tex>b_n = f_n \cdot f_{n+1} = f_n(f_{n-1} + f_n ) = f_{n -1} \cdot f_n + f_n^2= b_{n-1} + g_n.</tex><br> <br><tex>\begin{array}{ll} b_0 = 1 \\b_n = b_{n- 1} + g_n, \quad n\geqslant1.\\\end{array}</tex><br> Приведём суммы к замкнутому виду:<br><tex>\begin{array}{ll}B(z) = \displaystyle\sum_{n=0}^{\infty}b_nz^n = 1 + \displaystyle\sum_{n=1}^{\infty}(b_{n-1} + g_n)z^n, \\B(z) = 1 + \displaystyle\sum_{n=1}^{\infty}b_{n-1}z^n + \displaystyle\sum_{n=1}^{\infty}g_nz^n, \\B(z) = 1 + z\displaystyle\sum_{n=1}^{\infty}b_{n-1}z^{n-1} + \displaystyle\sum_{n=1}^{\infty}g_nz^n, \\B(z) = 1 + z\displaystyle\sum_{n=0}^{\infty}b_nz^n + (\displaystyle\sum_{n=0}^{\infty}g_nz^n - 1), \\B(z) = zB(z) + G(z), \\B(z)(1 - z) = G(z), \\\end{array}</tex><br>откуда получаем замкнутое выражение для производящей функции:<br><tex>B(z) = \dfrac{G(z)}{1 - z} = \dfrac{1}{1 - 2z - 2z^2 + z^3} = A(z).</tex><br> Производящие функции <tex>A(z)</tex> и <tex>B(z)</tex> равны <tex>\Rightarrow</tex> почленно равны задаваемые ими последовательности <tex>f_0^2, f_1^2, f_2^2, \ldots</tex> и <tex>f_0 \cdot f_1, f_1 \cdot f_2, f_2 \cdot f_3, \ldots</tex>, а значит, и исходное равенство <tex>f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_n \cdot f_{n+1}</tex>выполняется.
==См. также==
