Использование производящих функций для доказательства тождеств

Материал из Викиконспекты
Перейти к: навигация, поиск

В дальнейшем будем обозначать [math][x^n]A(x)[/math] коэффициент при [math]x^n[/math] в формальном степенном ряде [math]A(x)[/math]


Задача:
Доказать, что [math]\sum\limits_{i = 0}^{2n} (-1)^i \cdot (i + 1) \cdot (2n + 1 - i) = n + 1[/math]


Докажем, что [math]\sum\limits_{i = 0}^{2n} (-1)^i \cdot (i + 1) \cdot (2n + 1 - i) = 1 \cdot (2n + 1) - 2 \cdot (2n) + 3 \cdot (2n - 1) + \ldots + (2n + 1) \cdot 1 = n + 1[/math]

Рассмотрим известную нам производящую функцию

[math]A(x) = \dfrac{1}{1 - x} = 1 + x + x^2 + \ldots = \sum\limits_{n = 0}^{\infty}x^n[/math]

Возводя её в квадрат, по определению произведения формальных степенных рядов, получаем [math]A^2(x) = \dfrac{1}{1 - x} \cdot \dfrac{1}{1 - x} = (\sum\limits_{n = 0}^{\infty}x^n) \cdot (\sum\limits_{n = 0}^{\infty}x^n) = [/math]

[math] = \sum\limits_{n = 0}^{\infty} x^n \cdot (\sum\limits_{i = 0}^{n}([x^i]A(x) \cdot [x^{n - i}]A(x))) = \sum\limits_{n = 0}^{\infty} x^n \cdot (\sum\limits_{i = 0}^{n}(1 \cdot 1)) = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n[/math]

То есть [math]\dfrac{1}{(1 - x)^2} = \sum\limits_{n = 0}^{\infty} (n + 1) \cdot x^n[/math]