|
Лекция 17
Формальные
степенные ряды и действия над ними. Производящие функции последовательностей.
Пусть  - числовая
последовательность; формальный степенной
ряд - это символ вида  , в котором числа называются коэффициентами, а символ  называется переменной. Фрагменты  степенного ряда
называются слагаемыми; когда
коэффициент  , слагаемое , т.е.  записывать
необязательно. Любой многочлен можно считать записью формального степенного
ряда, в котором все коэффициенты, начиная с какого-то номера, равны нулю.
Вместо символа часто пишут символ  . Два формальных степенных ряда и  считаются равными, если для каждого  выполняется равенство:
Над формальными степенными рядами
определяется некоторые действия, являющиеся обобщением арифметики многочленов.
Сложение. Пусть
 -
два формальных
степенных ряда от одной и той же переменной ; сложением этих
рядов называется действие, в результате которого возникает третий формальный
степенной ряд  , называемый суммой
рядов  и  , такой, что
 .
Таким образом,  . Нетрудно проверить, что для любых трех формальных степенных
рядов  имеет место равенство:
 ,
а для любых двух
формальных степенных рядов  справедливо равенство:
Из сказанного следует, что
формальный степенной ряд  играет в определенном
только что сложении роль нуля. Кроме того, если - формальный степенной
ряд, то ряд  играет роль противоположного элемента:  .
Вычитание. Если
- два формальных
степенных ряда, то ряд , получаемый по правилу  , называется разностью,
а действие, создающее разность,
называется вычитанием. Очевидно, что
вычитание - это прибавление противоположного ряда.
Умножение. Пусть
два формальных
степенных ряда; построим третий формальный степенной ряд , который будет называться произведением рядов и , а действие, приводящее к произведению, будет называться умножением:
Для умножения
сохраняется традиционная символика: произведение  рядов и записывается в виде  . Ясно, что для любых трех рядов справедливы равенства:
Ряд  обладает, очевидно,
тем свойством, которое присуще в числовом умножении единице: для любого
формального степенного ряда имеет место равенство:
 . Если для некоторых двух формальных степенных рядов и выполняется равенство  , то эти ряды называются обратными
по отношению к друг другу. Пишут 
Деление. Это действие,
которое по двум формальным степенным рядам
при обязательном
предположении -  - создает третий ряд такой, чтобы оказалось
выполненным равенство:  . Расписываем последнее равенство по коэффициентам:
 следовательно  ;
 следовательно  ;
.................................................................
 следовательно  ;
..........................................................................................
Ряд называется частным от деления ряда
на ряд ; часто пишут:  .
Заметим для примера:
И последнее определение. Формальный
степенной ряд называется производящей функцией последовательности
. Действия над формальными степенными рядами, определенные
выше, это - и действия над производящими функциями.
Пример
использования техники действий над производящими функциями будет приведен в
следующей лекции.
Лекция 18
Линейные
рекуррентные соотношения и их решение с помощью производящих функций. Числа
Фибоначчи.
Пусть  - числовая
последовательность со следующим свойством:
 ,
причем последнее
равенство верно для всех  , число  считается фиксированным,
а числа  считаются изначально
заданными. Таким образом, данная последовательность полностью определяется
своими первыми членами  ; равенство, благодаря которому это оказывается возможным,
называется линейным рекуррентным
соотношением.
Имеется следующая классическая
задача: как выразить общий член  данной
последовательности не через предыдущие члены последовательности, а в виде
аналитического выражения от ? Приведем решение этой задачи с помощью производящий
функций.
Пусть  - производящая функция
данной последовательности , которая задается линейным рекуррентным соотношением . Фиксируем следующий
формальный степенной ряд:  (здесь все
коэффициенты, начиная с  -й степени переменной , равны нулю). Вычислим произведение  :
Таким образом,
формальный степенной ряд - это тоже многочлен,
так что производящая функция представляется как
частное от деления двух многочленов:
 .
Существует
техника разложения таких выражений «на простейшие дроби», с помощью которой
можно вычислить коэффициенты дроби  в конечном виде как
функции от номера коэффициента. Это и есть полное формальное решение
рассматриваемой задачи. Рассмотрим пример.
Пусть  и  Такая
последовательность называется числами
Фибоначчи. Последовательность чисел Фибоначчи выгляди так:
1,1,2,3,5,8,13,21... . Найдем -е число Фибоначчи как функцию от . Имеем:  и, продолжая сохранять
обозначения,  ; отсюда  имеет вид:
 ;
следовательно,
 .
Заметим:  , где  ; следовательно, 
в соответствии с
правилом деления формальных степенных рядов:
Отсюда следует,
что
|
