суммы и рекуррентности

суммы и рекуррентности Рекуррентные соотношения и производящие функции 1. Производящие функции и действия над ними Определение. Пусть  (целых, рациональных, вещественных или комплексных). Производящей функцией  (производящим рядом) называется запись вида  — произвольная (бесконечная) последовательность чисел   в точке    Замечание. Не следует думать, что мы можем сказать, чему равно значение производящей  функции  . Переменная   является формальной, и ряд  смысла не имеет. Единственное, что мы можем сказать про функцию  значение в нуле равно  коэффициенты кроме конечного числа равны нулю), то значение этого ряда в любой точке  выражается конечной суммой и поэтому имеет смысл. . Если, однако, производящий ряд является полиномом (т.е. все его  , это что ее  Определение. Суммой двух производящих функций  и  называется производящая функция Произведением производящих функций   и   называется производящая функция Определение. Пусть  производящие функции, причем  функцию   называется производящая функция  и   — две  . Подстановкой производящей функции   в  Если, например  , то  Очевидно, что если обе производящие функции являются многочленами, то определения  суммы, произведения и подстановки производящих функций совпадают с определениями  суммы, произведения и подстановки многочленов.2. Элементарные производящие функции Поскольку неудобно каждый раз записывать производящую функцию в виде ряда, то для  некоторых часто встречающихся функций введены сокращенные записи. Определение. где   — произвольное комплексное число. Коэффициент при   в этой записи называется числом сочетаний из   по   и обозначается    или  . При натуральном значении  степени многочлена. Пользуясь этим, можно получить простейшие комбинаторные  тождества. Подставляя, например,   часть 1) определения совпадает с обычным определением   и  , получаем тождества: Между введенными функциями имеются соотношения, которые также связаны с  комбинаторными тождествами. Докажем, например, что Действительно, свободный член произведения равен  , а при   получаем что совпадает с левой частью равенства 2) при  , откуда получаем требуемое. Можно также доказать следующие равенства (сделайте это самостоятельно):3. Деление производящих функций С делением производящих функций дело обстоит сложнее. Так, например, не существует  формального степенного ряда  , такого, что  . Утверждение. Пусть  существует единственный формальный степенной ряд   — формальный степенной ряд, такой, что  , такой, что  . Тогда  . Доказательство. Проведем доказательство по индукции.  коэффициенты ряда  степени  уравнение относительно  решение.  определяется из условия   вплоть до степени  , причем  . Пусть теперь все   однозначно определены. Коэффициент при  . Это линейное  . Поэтому это уравнение имеет единственное  Замечание. Только что доказанное утверждение очевидно неверно, если мы рассматриваем  формальные степенные ряды с целыми коэффициентами. Оно будет верно только в том  случае, если  . 4. Производящая функция для последовательности чисел Фибоначчи Последовательность чисел Фибоначчи определяется соотношением  ,  . Ее члены  функцию для этой последовательности.  при   Выведем производящую  Определяющее соотношение для последовательности означает, что ее производящая  функция  соотношению  удовлетворяет  , откуда  . Представим дробь в виде суммы простейших дробей:здесь  Отсюда . Здесь мы воспользовались тем, что  . 5. Числа Каталана Еще одна известная последовательность: последовательность  Каталана   Она задается соотношением  ,  получаем  . Так, например, при  .   Рассмотрим производящую функцию для чисел Каталана: Определяющее соотношение для производящей функции означает, что она удовлетворяет  следующему уравнению: из которого легко найти саму производящую функцию Этот вид производящей функции позволяет найти формулу для чисел Каталана. Согласно  общей формуле бинома Ньютона имеемили, умножая числитель и знаменатель на   и сокращая на  , получаем Эта формула дает и более простое рекуррентное соотношение для чисел Каталана: 6. Рациональные производящие функции Теорема. Пусть последовательность  соотношением порядка   задается линейным рекуррентным  и числа   фиксированы. Тогда производящая  функция  многочлена   равна  , а степень   не превосходит  .  рациональна,  , причем степень  Доказательство теоремы, по существу, повторяет рассуждение для чисел Фибоначчи.  Рекуррентное соотношение можно переписать в виде уравнения на производящую функцию: Разрешая это линейное уравнение относительно  , получаем утверждение теоремы. Оказывается, что и наоборот, последовательность коэффициентов всякой рациональной  производящей функции удовлетворяет рекуррентному соотношению. Теорема. Пусть  меньше  . Тогда коэффициенты производящей функции  рекуррентному соотношению с постоянными коэффициентами. , причем степень многочлена   равна  , а степень     удовлетворяют линейному  Скажем несколько слов о производящих функциях несколько более общего вида. Пусть   и степень многочлена   не меньше степени многочлена  .  Тогда  меньше степени   можно представить в виде   уже  . Тем самым, по предыдущей теореме, коэффициенты данной функции  , и степень многочленаудовлетворяют линейному рекуррентному соотношению, начиная с некоторого номера.  Обратное утверждение, очевидно, тоже справедливо. 7. Произведение Адамара рациональных производящих функций Определение. Произведением Адамара производящих функций  и  называется производящая функция Таким образом, произведение Адамара двух последовательностей — это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Лемма. Производящая функция для последовательности  только тогда, когда существуют такие числа  многочлены  , что начиная с некоторого номера   и такие   рациональна тогда и  Выражение в правой части этого равенства называется квазимногочленом от переменной  . Доказательство. Заметим прежде всего, что производящая функция   имеет вид Коэффициент при   в этой производящей функции равен  степени   — многочлен от  где  представляется виде линейной комбинации многочлена и простейших дробей вида  , поэтому коэффициенты соответствующей производящей функции являются  квазимногочленами. . Всякая рациональная функция от переменнойНаоборот, предположим, что коэффициенты производящей функции, начиная с некоторого  номера, представляются в виде квазимногочлена. Покажем, что в случае  квазимногочлена   соответствующая производящая функция рациональна.  равна  . Многочлены  Пусть степень многочлена  , коэффициенты  которых определяются равенством, приведенным выше, образуют базис в пространстве  многочленов степени не выше  степеней  представляется в виде линейной комбинации многочленов  производящая функция есть просто линейная комбинация функций  Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого  вида при различных   образует базис в этом пространстве. Поэтому многочлен    , и соответствующая  . Действительно, любая последовательность многочленов  ,  .  . Лемма доказана. Теорема. Произведение Адамара двух рациональных производящих функций рационально. Доказательство. Принимая в расчет лемму, для доказательства теоремы осталось заметить,  что произведение квазимногочленов является квазимногочленом. Это утверждение  непосредственно вытекает из формулы, приведенной в лемме. 8. Дифференцирование и интегрирование производящих функций Определение. Пусть  этой функции называется функция  — производящая функция. Производной  Интегралом этой функции называется функция Замечание. Нетрудно видеть, что для функций, представимых в виде степенных рядов,  формула для производной соответствует обычной. Формула для интеграла соответствует  значению интеграла с переменным верхним пределом Это позволяет находить производящие функции для большого числа разнообразных  последовательностей. Найдем, например, производящую функциюЛегко видеть, что поэтому Задачи. 1. Решите последовательности а)  б)  ,  ,  ,  . ,  ,  ,  . 2. Докажите равенства (3)–(7). 3. Найдите производящие функции для последовательностей ; ; а)  б)  в)  . 4. Рациональны ли производящие функции для последовательностей а)  б)  ; ? 5. Пусть  последовательности   — производящая функция для   Найдите производящие функции для последовательностей а)  б)  ; 6. Пользуясь производящей функцией для чисел Фибоначчи, доказать для них тождества а)  б)  ; ;в)  г)  ; . 7. Пусть  . Докажите, что Докажите, что  . 8. Последовательность   такова, что Найдите  . 9. Пусть  . Найдите рекуррентное уравнение Оцените сходимость и вычислите  . 10. Пусть Доказать, что для некоторого    . 11. Доказать, что при любых натуральных  — целые числа, удовлетворяющие рекуррентному соотношению 12. ПустьДокажите, что