Комбинаторные алгоритмы для программистов



             

Применение степенных рядов для доказательства тождеств


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

x
в обоих рядах должны совпадать. Это и приводит к доказываемому тождеству.

Рассмотрим, например, известное нам разложение

\frac{1}{{1 - x}} = 1 + x + x^2 + \ldots + x^n + \ldots

Возведя обе части этого разложения в квадрат, получаем

\frac{1}{{(1 - x)^2 }} = 1 + 2x + 3x^2 + \ldots + (n + 1)x^n + \ldots

(10.1)

Если заменить здесь

x
на –
x
, то получим, что

 \frac{1}{{(1 + x)^2 }} = 1 - 2x + 3x^2 - \ldots + ( - 1)^n (n + 1)x^n + \ldots

(10.2)

Перемножив разложения (10.1) и (10.2), выводим, что

 \begin{gathered} \frac{1} {{(1 - x)^2 }}\frac{1} {{(1 + x)^2 }} = 1 + [1( - 2) + 2 \cdot 1]x + [1 \cdot 3 + 2( - 2) + 3 \cdot 1]x^2 + \hfill \\ \ldots + [1( - 1)^n (n + 1) + 2( - 1)^{n - 2} n + \ldots + ( - 1)^n (n + 1) \cdot 1]x^n + \ldots \hfill \\ \end{gathered}

(10.3)

Очевидно, что коэффициенты при нечетных степенях

x
обращаются в нуль, каждое слагаемое дважды входит в эти коэффициенты с противоположными знаками. Коэффициент же
x^{2n}
равен

 1(2n + 1) - 2 \cdot 2n + 3(2n - 1) - \ldots + (2n + 1).

Но функцию

\frac{1}{{(1 - x)^2 (1 + x)^2 }}
можно разложить в степенной ряд и иным образом. Мы имеем

\frac{1}{{(1 - x)^2 (1 + x)^2 }}=\frac{1}{{(1 - x^2 )^2 }},

А разложение для

\frac{1}{{(1 - x^2 )^2 }}
получается из разложения (10.1), если заменить в нем
x
на
x^2
:

 \frac{1}{{(1 - x^2 )^2 }}=1 + 2x^2 + 3x^4 + \ldots + (n + 1)x^{2n} +....

(10.4)

Мы знаем, что никакая функция не может иметь двух различных разложений в степенные ряды. Поэтому коэффициент при

x^{2n}

разложении (10.3) должен равняться коэффициенту при

x^{2n}

в разложении (10.4). Отсюда вытекает следующее тождество:

1(2n + 1) - 2 \cdot 2n + 3(2n - 1) - \ldots + (2n + 1)=n + 1.




Содержание    Вперед