Производящие функции и рекуррентные соотношения

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

С помощью степенных рядов можно доказывать многие тождества. Для этого берут некоторую функцию и двумя способами разлагают ее в степенной ряд. Поскольку функция может быть представлена лишь единственным образом в виде степенного ряда, то коэффициенты при одинаковых степенях $$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$$ Если заменить здесь $$x$$ на – $$x$$, то получим, что$$\frac{1}{{(1 + x)^2 }} = 1 - 2x + 3x^2 - \ldots + ( - 1)^n (n + 1)x^n + \ldots$$ Перемножив разложения (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}$$

Очевидно, что коэффициенты при нечетных степенях $$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} +....$$ Мы знаем, что никакая функция не может иметь двух различных разложений в степенные ряды. Поэтому коэффициент при $$x^{2n}$$ разложении (10.3) должен равняться коэффициенту при $$x^{2n}$$ в разложении (10.4). Отсюда вытекает следующее тождество:$$1(2n + 1) - 2 \cdot 2n + 3(2n - 1) - \ldots + (2n + 1)=n + 1.$$

Производящие функции

Пусть дана некоторая последовательность чисел $$a_0,a_1,\ldots,a_n,\ldots$$. Образуем степенной ряд$$a_0 + a_1 x + \ldots + a_n x^n + \ldots.$$ Если этот ряд сходится в какой-то области к функции $$f(x)$$, то эту функцию называют производящей для последовательности чисел $$a_0,a_1,\ldots,a_n,\ldots$$ Например, из формулы$$\frac{1}{{1 - x}} = 1 + x + \ldots + x^n + \ldots$$ вытекает, что функция $$\frac{1} {{1 - x}}$$ является производящей для последовательности чисел. А формула (10.1) показывает, что для последовательности чисел $$1, 2, 3, 4, ..., n, ..$$. производящей является функция $$\frac{1} {{(1 - x)^2 }}$$.

Нас будут интересовать производящие функции для последовательностей $$a_0, a_1,\ldots,a_n,\ldots$$, так или иначе связанных с комбинаторными задачами. С помощью таких функций удается получить самые разные свойства этих последовательностей. Кроме того, мы рассмотрим, как связаны производящие функции с решением рекуррентных соотношений.

Бином Ньютона

Получим производящую функцию для конечной последовательности чисел $$C_n^0,C_n^1,\ldots,C_n^n$$. Известно, что$$(a + x)^2 = a^2 + 2ax + x^2$$ и$$(a + x)^3 = a^3 + 3a^2 x + 3ax^2 + x^3.$$ Эти равенства являются частными случаями более общей формулы, дающей разложение для $$(a + x)^n$$. Запишем $$(a + x)^n$$ в виде$$(a + x)^n = \underbrace{(a + x)(a + x)\ldots (a + x)}_{n \text{ раз}}.$$ Раскроем скобки в правой части этого равенства, причем будем записывать все множители в том порядке, в котором они нам встретятся. Например, $$(a +x)^2$$ запишем в виде$$(a + x)^2 = (a + x)(a + x) = aa + ax + xa + xx,$$ а $$(a + x)^3$$ - в виде$$(a + x)^3 = (a + x)(a + x)(a + x) =\\= aaa + aax + axa + axx + xaa + xax + xxa + xxx.$$ Видно, что в формулу (10.5) входят все размещения с повторениями, составленные из букв $$x$$ и $$a$$ по две буквы в каждом размещении, а в формулу (10.6) - размещения с повторениями из тех же букв, но состоящие из трех букв каждое. То же самое и в общем случае — после раскрытия скобок в формуле (10.4) мы получим всевозможные размещения с повторениями букв $$x$$ и $$a$$, состоящие из $$n$$ элементов. Приведем подобные члены. Подобными будут члены, содержащие одинаковое количество букв $$x$$ (тогда и букв $$a$$ в них будет поровну). Найдем, сколько будет членов, в которые входит $$k$$ букв $$x$$ и, следовательно, $$n - k$$ букв $$a$$. Эти члены являются перестановками с повторениями, составленными из $$k$$ букв $$x$$ и $$n - k$$ букв $$a$$. Поэтому их число равно$$P(k,n - k) = C_n^k = \frac{{n!}}{{k!(n - k)!}}.$$ Отсюда вытекает, что после приведения подобных членов выражение $$x^k a^{n - k}$$ войдет с коэффициентом $$C_n^k = \frac{{n!}}{{k!(n - k)!}}$$. Итак, мы доказали, что$$(a + x)^n = C_n^0 a^n + C_n^1 a^{n - 1} x + \ldots + C_n^k a^{n - k} x^k + \ldots + C_n^n x^n.$$ Равенство (10.7) принято называть формулой бинома Ньютона. Если положить в этом равенстве $$a = 1$$, то получим$$(1 + x)^n = C_n^0 + C_n^1 x + \ldots + C_n^k x^k + \ldots + C_n^n x^n.$$ Мы видим, что $$(1 + x)^n$$ является производящей функцией для чисел $$C_n^k$$, $$k = 0,1,\ldots$$. С помощью этой производящей функции можно сравнительно просто доказать многие свойства чисел $$C_n^k$$.

Ряд Ньютона

Мы назвали, как это обычно делают, формулу $$(a + x)^n$$ биномом Ньютона. Это наименование с точки зрения истории математики неверно. Формулу для $$(a + x)^n$$ хорошо знали среднеазиатские математики Омар Хайям, Гиясэдди и другие. В Западной Европе задолго до Ньютона она была известна Блэзу Паскалю. Заслуга же Ньютона была в ином - ему удалось обобщить формулу $$(a + x)^n$$ на случай нецелых показателей. Именно, он доказал, что если $$a$$ - положительное число и $$\left| x \right| < a$$, то для любого действительного значения $$\alpha$$ имеет место равенство$$\begin{gathered} (x + a)^\alpha = a^\alpha + \alpha a^{\alpha - 1} x + \frac{{\alpha (\alpha - 1)}} {{1 \cdot 2}}a^{\alpha - 2} x^2 + \ldots \\ \ldots + \frac{{\alpha (\alpha - 1)\ldots (\alpha - k + 1)}} {{1 \cdot 2\ldots k}}a^{\alpha - k} x^k + \ldots \end{gathered}$$ Только теперь получилось не конечное число слагаемых, а бесконечный ряд. В случае, когда $$n$$ - натуральное число, $$(n - n)$$ обращается в нуль. Но эта скобка входит в коэффициент всех членов, начиная с $$(n + 2)$$ -го, и потому все эти члены разложения равны нулю. Поэтому при натуральном $$n$$ ряд (10.9) превращается в конечную сумму.

Производящие функции и рекуррентные соотношения

Теория производящих функций тесно связана с рекуррентными соотношениями. Вернемся снова к делению многочленов. Пусть функции $$f(x)$$ и $$\varphi (x)$$ разложены в степенные ряды,$$f\left( x \right) = a_0 + a_1 x + \ldots a_n x^n + \ldots$$ $$\varphi (x) = b_0 + b_1 x + \ldots b_n x^n \ldots$$ - два многочлена, причем $$b_0 \ne 0$$. Мы будем, кроме того, предполагать, что $$n < m$$, то есть, что алгебраическая дробь $$\frac{{f(x)}}{{\varphi (x)}}$$ правильна (в противном случае мы всегда можем выделить из нее целую часть). Мы знаем, что если$$\frac{{f(x)}} {{\varphi (x)}} = c_0 + c_{1x} x + \ldots + c_k x^k + \ldots,$$ то$$a_0 + a_1 x + \ldots + a_n x^n =$$ $$= (b_0 + b_1 x + \ldots + b_m x^m )(c_0 + c_1 x + \ldots + c_k x^k + \ldots ).$$ Раскроем в правой части этого равенства скобки и сравним коэффициенты при одинаковых степенях $$x$$ слева и справа. Сначала мы получим $$m$$ соотношений такого вида:$$\begin{gathered} b_0 c_0 = a_0,\\ b_0 c_1 + b_1 c_0 = a_1,\\ b_0 c_2 + b_1 c_1 + b_2 c_0 = a_2,\\ .....................\\ b_0 c_{m - 1} + b_1 c_{m - 2} + \ldots + b_{m - 1} c_0 = a_{m - 1} \end{gathered}$$ (если $$n < m - 1$$, то мы считаем, что $$a_{n + 1} = \ldots = a_{m - 1} = 0$$ ). А дальше все соотношения имеют один и тот же вид:$$b_0 c_{m + k} + b_1 c_{m + k - 1} + \ldots + b_m c_k = 0 ,\quad k = 0,1\ldots.$$ (ведь в $$f(x)$$ нет членов, содержащих $$x^m,x^{m + 1}$$ и т.д.). Таким образом, коэффициенты $$c_0,c_1,\ldots,c_k,\ldots$$ ряда (10.10) удовлетворяют рекуррентному соотношению (10.12). Коэффициенты этого соотношения зависят лишь от знаменателя дроби. Числитель же дроби нужен для нахождения первых членов $$c_0,c_1,\ldots,c_{m-1}$$ рекуррентной последовательности.

Обратно, если дано рекуррентное соотношение (10.12) и заданы члены $$c_0,c_1,\ldots,c_{m-1}$$, то мы сначала по формулам (10.11) вычислим значения $$a_0,\ldots,a_{m - 1}$$. А тогда производящей функцией для последовательности чисел $$c_0,c_1,\ldots,c_k,\ldots$$ является алгебраическая дробь$$\frac{{f(x)}} {{\varphi (x)}} = \frac{{a_0 + ax + \ldots + a_{m - 1} x^{m - 1} }} {{b_0 + b_1 x + \ldots + b_m x^m }}.$$ На первый взгляд кажется, что мы мало выиграли при замене рекуррентного соотношения производящей функции. Ведь все равно придется делить числитель на знаменатель, а это приведет к тому же самому рекуррентному соотношению (10.12). Но дело в том, что над дробью (10.13) можно выполнять некоторые алгебраические преобразования, а это облегчит отыскание чисел $$c_k$$.

Об едином нелинейном рекуррентном соотношении

При решении задачи о разбиении последовательности мы пришли к рекуррентному соотношению$$T_n = T_0 T_{n - 1} + T_1 T_{n - 2} + \ldots + T_{n - 1} T_0,$$ где $$T_0 = 1$$.Покажем, как решить соотношение (10.14). Для этого составим производящую функцию.$$f(x) = T_0 + T_1 x + T_2^{} x^2 + \ldots + T_n x^n + \ldots$$ Положим$$F(x) \equiv xf(x) = T_0 x + T_1 x^2 + \ldots + T_n x^{n + 1} + \ldots$$ и возведем $$F(x)$$ в квадрат. Мы получим, что$$F^2 (x) = T_0^2 + (T_0 T_1 + T_1 T_0 )x^3 + \ldots$$ $$...+ (T_0 T_{n - 1} + \ldots + T_{n - 1} T_0 )x^{n + 1} + \ldots$$

Но по рекуррентному соотношению (10.14),$$T_0 T_{n - 1} + \ldots + T_{n - 1} T_0 = T_n.$$ Значит,$$F^2 (x) = T_1 x^2 + T_2 x^3 + \ldots + T_n x^{n + 1}.$$ Полученный ряд есть не что иное, как $$F(x) - T_0 x$$ ; поскольку $$T_0 = 1$$, он равен$$F^2 (x) = F(x) - x.$$ Для функции $$F(x)$$ получилось квадратное уравнение (10.17). Решая его, находим, что$$F(x) = \frac{{1 - \sqrt {1 - 4x} }}{2}.$$ Мы выбрали перед корнем знак минус, так как в противном случае при $$x =0$$ мы имели бы $$F(0) = 2$$, а из разложения (10.16) видно, что $$F(0) = 0$$.