МАТЕМАТИЧНІ ШКІЛЬНІ ОЛІМПІАДИ.: Рекуретні відношення. Ряди та їх функції(рос.мова)

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

1. Производящие функции и действия над ними

Определение. Пусть $a_0,a_1,a_2,\ldots$ — произвольная (бесконечная) последовательность чисел (целых, рациональных, вещественных или комплексных). Производящей функцией (производящим рядом) называется запись вида

$\displaystyle A(s)=a_0+a_1s+a_2s^2+\ldots=\sum_{n=0}^{\infty}a_ns^n .$

Замечание. Не следует думать, что мы можем сказать, чему равно значение производящей функции

в точке

. Переменная

является формальной, и ряд $a_0+a_1s_0+a_2s_0^2+\ldots$ смысла не имеет. Единственное, что мы можем сказать про функцию A(s)

, это что ее значение в нуле равно a_0

. Если, однако, производящий ряд является полиномом (т.е. все его коэффициенты кроме конечного числа равны нулю), то значение этого ряда в любой точке выражается конечной суммой и поэтому имеет смысл.

Определение. Суммой двух производящих функций

$A(s)=a_0+a_1s+a_2s^2+\ldots$ и $B(s)=b_0+b_1s+b_2s^2+\ldots$

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

$A(s)+B(s)=(a_0+b_0)+(a_1+b_1)s+(a_2+b_2)s^2+\ldots$

Произведением производящих функций

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

$A(s)B(s)=a_0b_0+(a_0b_1+a_1b_0)s+(a_0b_2+a_1b_1+a_2b_0)s^2+\ldots$

Определение. Пусть $A(s)=a_0+a_1s+a_2s^2+\ldots$ и $B(s)=b_1s+b_2s^2+\ldots$ — две производящие функции, причем B(0)=0

. Подстановкой производящей функции

в функцию

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

$A(B(s))=a_0+a_1b_1s+ (a_1b_2+a_2b_1^2)s^2+(a_1b_3+2a_2b_1b_2+a_3b_1^3)s^3+\ldots$

Если, например B(s)=-s

, то $A(B(s))=a_0-a_1s+a_2s^2-\ldots$

Очевидно, что если обе производящие функции являются многочленами, то определения суммы, произведения и подстановки производящих функций совпадают с определениями суммы, произведения и подстановки многочленов.

2. Элементарные производящие функции

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

Определение.

$\displaystyle {\rm 1)}\ (1+s)^{\alpha}=1+\alpha s+{\alpha(\alpha-1)\over 2!}s^2+{\alpha(\alpha-1)(\alpha-2)\over 3!}s^3+\ldots,$

где $\alpha$ — произвольное комплексное число.

Коэффициент при s^n

в этой записи называется числом сочетаний из $\alpha$ по

и обозначается ${\sf C}_{\alpha}^n$ или $\left(\begin{array}{c} \alpha\\ n \end{array}\right)$ .

$\begin{array}{l} \displaystyle {\rm 2)}\ e^s=1+s+{s^2\over 2!}+{s^3\over 3!}+\ldots\\[3mm] \displaystyle {\rm 3)}\ \ln{1\over 1-s}=s+{s^2\over 2}+{s^3\over 3}+\ldots\\[3mm] \displaystyle {\rm 4)}\ \sin s=s-{s^3\over 3!}+{s^5\over 5!}-\ldots\\[3mm] \displaystyle {\rm 5)}\ \cos s=1-{s^2\over 2!}+{s^4\over 4!}-\ldots \end{array}$

При натуральном значении $\alpha$ часть 1) определения совпадает с обычным определением степени многочлена. Пользуясь этим, можно получить простейшие комбинаторные тождества. Подставляя, например, s=1

, получаем тождества:

$\begin{array}{l} 1+\alpha+{\sf C}_{\alpha}^2+{\sf C}_{\alpha}^3+\ldots+{\sf C}_{\alpha}^{\alpha}=2^{\alpha},\\ 1-\alpha+{\sf C}_{\alpha}^2-{\sf C}_{\alpha}^3+\ldots+(-1)^{\alpha}{\sf C}_{\alpha}^{\alpha}=0. \end{array}$

Между введенными функциями имеются соотношения, которые также связаны с комбинаторными тождествами. Докажем, например, что

$e^se^{-s}=1.$

Действительно, свободный член произведения равен

, а при

получаем

$\displaystyle {1\over n!0!}-{1\over (n-1)!1!}+{1\over (n-2)!2!}-\ldots+{(-1)^n\over 0!n!},$

что совпадает с левой частью равенства 2) при $\alpha=n$ , откуда получаем требуемое.

Можно также доказать следующие равенства (сделайте это самостоятельно):

$\begin{array}{l} 1)\ \sin^2 s+\cos^2 s=1,\\ 2)\ (1+s)^{\alpha}(1+s)^{\beta}=(1+s)^{\alpha+\beta},\\ 3)\ e^{\ln(1-s)^{-1}}=(1-s)^{-1},\\ \displaystyle 4)\ \ln(1+s)=s-{1\over 2}s^2+{1\over 3}s^3-\ldots+{(-1)^{n+1}\over n}s^n+\ldots,\\[3mm] 5)\ \ln(1-s)^{-\alpha}=\alpha\ln(1-s)^{-1} \end{array}$

3. Деление производящих функций

С делением производящих функций дело обстоит сложнее. Так, например, не существует формального степенного ряда B(s)

, такого, что sB(s)=1

Утверждение. Пусть A(s)

— формальный степенной ряд, такой, что $A(0)\ne0$ . Тогда существует единственный формальный степенной ряд B(s)

, такой, что A(s)B(s)=1

Доказательство. Проведем доказательство по индукции. b_0=1/a_0

. Пусть теперь все коэффициенты ряда

вплоть до степени

однозначно определены. Коэффициент при степени n+1

определяется из условия $a_0b_{n+1}+a_1b_n+\ldots+a_{n+1}b_0=0$ . Это линейное уравнение относительно $b_{n+1}$ , причем $a_0\ne0$ . Поэтому это уравнение имеет единственное решение.

Замечание. Только что доказанное утверждение очевидно неверно, если мы рассматриваем формальные степенные ряды с целыми коэффициентами. Оно будет верно только в том случае, если $a_0=\pm1$ .

4. Производящая функция для последовательности чисел Фибоначчи

Последовательность чисел Фибоначчи определяется соотношением f_0=0,f_1=1

, $f_{n+2}=f_{n+1}+f_n$ при $n\ge0$ . Ее члены $0,1,1,2,3,5,8,13,21,\ldots$ Выведем производящую функцию для этой последовательности.

Определяющее соотношение для последовательности означает, что ее производящая функция $Fib(s)=s+s^2+2s^3+3s^4+5s^5+\ldots$ удовлетворяет соотношению (Fib(s)-s)/s=Fib(s)+Fib(s)s

, откуда

Представим дробь в виде суммы простейших дробей:

$\begin{array}{l} \displaystyle {s\over 1-s-s^2}=-{5+\sqrt{5}\over 10s_1}\cdot{1\over 1-{s\over s_1}}- {5-\sqrt{5}\over 10s_2}\cdot{1\over 1-{s\over s_2}}=\\[5mm] \displaystyle =-{5+\sqrt{5}\over 10\cdot{-1-\sqrt{5}\over 2}}\left(1+{s\over s_1}+{s^2\over s_1^2}+\dots\right)-{5-\sqrt{5}\over 10\cdot{-1+\sqrt{5}\over 2}}\left(1+{s\over s_2}+{s^2\over s_2^2}+\ldots\right)=\\[5mm] \displaystyle =-{1\over \sqrt{5}}\left(1+{s\over s_1}+{s^2\over s_1^2}+\ldots\right)+ {1\over \sqrt{5}}\left(1+{s\over s_2}+{s^2\over s_2^2}+\ldots\right), \end{array}$

здесь $s_1=-(1+\sqrt{5})/2,s_2=(-1+\sqrt{5})/2$ .

Отсюда

$\begin{array}{l}\displaystyle f_n={1\over \sqrt{5}}(s_2^{-n}-s_1^{-n})={(-1)^n\over \sqrt{5}}(s_1^n-s_2^n)=\\[5mm] \displaystyle ={(-1)^n\over \sqrt{5}}\left(\left({-1-\sqrt{5}\over 2}\right)^n-\left({-1+\sqrt{5}\over 2}\right)^n\right). \end{array}$

Здесь мы воспользовались тем, что s_1s_2=-1

5. Числа Каталана

Еще одна известная последовательность: последовательность Каталана $1,1,2,5,14,42,132,\ldots$ Она задается соотношением c_0=1

, $c_{n+1}=c_0c_n+c_1c_{n-1}+c_2c_{n-2}+\ldots+c_nc_0$ . Так, например, при n=4

получаем $c_4=14=1\cdot5+1\cdot2+2\cdot1+5\cdot1$ .

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

$Cat(s)=c_0+c_1s+c_2s^2+c_3s^3+\ldots=1+s+2s^2+5s^3+14s^4+\ldots$

Определяющее соотношение для производящей функции означает, что она удовлетворяет следующему уравнению:

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

$\displaystyle Cat(s)={1-\sqrt{1-4s}\over 2s}.$

Этот вид производящей функции позволяет найти формулу для чисел Каталана. Согласно общей формуле бинома Ньютона имеем

$\displaystyle c_n={(1/2)(1/2)(3/2)\ldots((2n-1)/2)4^{n+1}\over 2(n+1)!},$

или, умножая числитель и знаменатель на

и сокращая на $2^{n+1}$ , получаем

$\displaystyle c_n={(2n)!\over n!(n+1)!}={1\over n+1}{\sf C}_{2n}^n.$

Эта формула дает и более простое рекуррентное соотношение для чисел Каталана:

$\displaystyle c_{n+1}=c_n{4n+2\over n+2}.$

6. Рациональные производящие функции

Теорема. Пусть последовательность $a_0,a_1,\ldots,a_k,\ldots$ задается линейным рекуррентным соотношением порядка

$a_{n+k}=c_{k-1}a_{n+k-1}+c_{k-2}a_{n+k-2}+\ldots+c_0a_n,$

и числа $a_0,a_1,\ldots,a_{k-1}$ фиксированы. Тогда производящая функция $A(s)=a_0+a_1s+a_2s^2+\ldots$ рациональна, $\displaystyle A(s)={P(s)\over Q(s)}$ , причем степень многочлена Q(s)

равна

, а степень P(s)

не превосходит k-1

Доказательство теоремы, по существу, повторяет рассуждение для чисел Фибоначчи. Рекуррентное соотношение можно переписать в виде уравнения на производящую функцию:

$\begin{array}{l} A(s)-a_{k-1}s^{k-1}a_{k-2}s^{k-2}-\ldots-a_0=\\ =c_{k-1}(A(s)-a_{k-2}s^{k-2}-a_{k-3}s^{k-3}-\ldots-a_0)s+\ldots+c_0A(s)s^k. \end{array}$

Разрешая это линейное уравнение относительно A(s)

, получаем утверждение теоремы.

Оказывается, что и наоборот, последовательность коэффициентов всякой рациональной производящей функции удовлетворяет рекуррентному соотношению.

Теорема. Пусть $\displaystyle A(s)={P(s)\over Q(s)}$ , причем степень многочлена Q(s)

равна

, а степень P(s)

меньше

. Тогда коэффициенты производящей функции A(s)

удовлетворяют линейному рекуррентному соотношению с постоянными коэффициентами.

Скажем несколько слов о производящих функциях несколько более общего вида.

Пусть $\displaystyle A(s)={P(s)\over Q(s)}$ и степень многочлена P(s)

не меньше степени многочлена Q(s)

. Тогда

можно представить в виде $\displaystyle A(s)=P_1(s)+{P_2(s)\over Q(s)}$ , и степень многочлена P_2(s)

уже меньше степени Q(s)

. Тем самым, по предыдущей теореме, коэффициенты данной функции удовлетворяют линейному рекуррентному соотношению, начиная с некоторого номера. Обратное утверждение, очевидно, тоже справедливо.

7. Произведение Адамара рациональных производящих функций

Определение. Произведением Адамара производящих функций

$A(s)=a_0+a_1s+a_2s^2+\ldots$ и $B(s)=b_0+b_1s+b_2s^2+\ldots$

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

$A\circ B(s)=a_0b_0+a_1b_1s+a_2b_2s^2+\ldots$

Таким образом, произведение Адамара двух последовательностей — это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей.

Лемма. Производящая функция для последовательности $a_0,a_1,a_2,\ldots$ рациональна тогда и только тогда, когда существуют такие числа $q_1,q_2,\ldots,q_l$ и такие многочлены $p_1(n),p_2(n),\ldots,p_l(n)$ , что начиная с некоторого номера

$a_n=p_1(n)q_1^n+p_2(n)q_2^n+\ldots+p_l(n)q_l^n .$

Выражение в правой части этого равенства называется квазимногочленом от переменной

Доказательство. Заметим прежде всего, что производящая функция $(1-qs)^{-k}$ имеет вид

$\begin{array}{l} (1-qs)^{-k}=1-\left(\begin{array}{r} -k\\ 1 \end{array}\right)qs+\left(\begin{array}{r} -k\\ 2 \end{array}\right)q^2s^2-\left(\begin{array}{r} -k\\ 3 \end{array}\right)q^3s^3+\ldots=\\[2mm] =1+\left(\begin{array}{r} k\\ 1 \end{array}\right)qs+\left(\begin{array}{c} k+1\\ 2 \end{array}\right)q^2s^2+\left(\begin{array}{c} k+2\\ 3 \end{array}\right)q^3s^3+\dots=\\[2mm] =1+\left(\begin{array}{c} k\\ k-1 \end{array}\right)qs+\left(\begin{array}{c} k+1\\ k-1 \end{array}\right)q^2s^2+\left(\begin{array}{c} k+2\\ k-1 \end{array}\right)q^3s^3+\ldots \end{array}$

Коэффициент при s^n

в этой производящей функции равен

$\displaystyle {(n+1)(n+2)\ldots(n+k-1)\over (k-1)!}q^n=P_{k-1}(n)q^n,$

где $P_{k-1}(n)$ — многочлен от

степени

. Всякая рациональная функция от переменной

представляется виде линейной комбинации многочлена и простейших дробей вида $(1-qs)^{-k_i}$ , поэтому коэффициенты соответствующей производящей функции являются квазимногочленами.

Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена p(n)q^n

соответствующая производящая функция рациональна.

Пусть степень многочлена

равна

. Многочлены $P_0,P_1,\ldots,P_{k-1}$ , коэффициенты которых определяются равенством, приведенным выше, образуют базис в пространстве многочленов степени не выше k-1

. Действительно, любая последовательность многочленов степеней $0,1,\ldots,k-1$ образует базис в этом пространстве. Поэтому многочлен

представляется в виде линейной комбинации многочленов P_i

, и соответствующая производящая функция есть просто линейная комбинация функций $(1-qs)^{-j}$ , $j=\overline{0,k-1}$ . Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при различных q_i

. Лемма доказана.

Теорема. Произведение Адамара двух рациональных производящих функций рационально.

Доказательство. Принимая в расчет лемму, для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы, приведенной в лемме.

8. Дифференцирование и интегрирование производящих функций

Определение. Пусть $A(s)=a_0+a_1s+a_2s^2+\ldots$ — производящая функция. Производной этой функции называется функция

$A^{\prime}(s)=a_1+2a_2s+3a_3s^2+\ldots+na_ns^{n-1}+\ldots$

Интегралом этой функции называется функция

$\displaystyle \int A(s)=a_0s+a_1{s^2\over 2}+a_2{s^3\over 3}+\ldots+a_n{s^{n+1}\over n+1}+\ldots$

Замечание. Нетрудно видеть, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

$\displaystyle \int A(s)=\int_0^sA(\xi)d\xi.$

Это позволяет находить производящие функции для большого числа разнообразных последовательностей. Найдем, например, производящую функцию

$\displaystyle f(s)={1\over 1\cdot2}+{s\over 2\cdot3}+{s^2\over 3\cdot4}+\ldots+{s^n\over (n+1)(n+2)}+\ldots$

Легко видеть, что

$\displaystyle (s^2f(s))^{\prime}=s+{1\over 2}s^2+{1\over 3}s^3+\dots=\ln(1-s)^{-1},$

поэтому

$\displaystyle f(s)=s^{-2}\int\ln(1-s)^{-1} =s^{-2}\left((s-1)\ln(1-s)^{-1}+s\right).$

Задачи.

1. Решите последовательности

а) $a_n=-2a_{n-1}+a_{n-2}+2a_{n-3}$ , a_1=-2

б) $a_n=a_{n-1}+a_{n-2}-a_{n-3}$ , a_1=-1

2. Докажите равенства (3)–(7).

3. Найдите производящие функции для последовательностей

а) $1,q,q^2,q^3,\ldots$ ;

б) $1,2,3,4,5,6,\ldots$ ;

в) $2,6,12,\ldots,(k+1)(k+2),\ldots$ .

4. Рациональны ли производящие функции для последовательностей

а) $1,4,9,16,\ldots,k^2,\ldots$ ;

б) $1,1/4,1/9,1/16,\ldots,1/k^2,\ldots$ ?

5. Пусть $A(s)=a_0+a_1s+a_2s^2+\ldots$ — производящая функция для последовательности $a_0,a_1,a_2,\ldots$ Найдите производящие функции для последовательностей

а) $a_0+a_1,a_1+a_2,a_2+a_3,a_3+a_4,\ldots$ ;