Тема №2 Рекуррентные последовательности и производящие функции
-
Введение
В комбинаторном анализе существует целый ряд подходов для изучения комбинаторных объектов и чисел:
- теоретико-множественный подход. Связан с вычислениями мощностей конечных множеств. Для решения таких вопросов необходима дополнительная информация, т.е. надо знать заранее мощности некоторых подмножеств (пример ‒ теорема включений и исключений).
- алгебраический подход. Основан на использовании вспомогательных, просто получаемых комбинаторных тождеств для нахождения интересующих исследователя комбинаторных чисел (пример ‒ метод рекуррентных соотношений).
- применений формул обращения. Формулы обращения связывают между собой различные комбинаторные числа и могут быть получены самыми различными способами.
- метод производящих функций. Используется для перечисления комбинаторных чисел и установления комбинаторных тождеств.
Рассмотрим один подход алгебраического подхода – метод рекуррентных соотношений.
Часто бывает удобно добавить к
последовательности
еще один элемент
и рассматривать последовательность
,
,
,
…,
,…
Иногда областью определения функции
служит множество из
первых натуральных чисел. Тогда множество
значений функции называется конечной
последовательностью длины
.
Последовательность
можно считать бесконечной последовательностью,
все члены которой, начиная с
-го,
равны нулю.
Для задания некоторых последовательностей используются рекуррентные соотношения. При таком способе задания последовательности указывают один или несколько первых членов и правило, которое позволяет найти ее n-ый член по предыдущим членам. Уточним понятия рекуррентной последовательности и рекуррентного соотношения.
2. Рекуррентные последовательности
Последовательности, в которых каждый член, начиная с некоторого, выражается через предыдущие, часто встречаются в математике и называются рекуррентными (от латинского recurrere – возвращаться) или возвратными.
Процесс вычисления членов этих последовательностей называется рекуррентным процессом.
.
Последовательность
называется рекуррентной (возвратной)
последовательностью порядка
,
если существует формула
,
(1)
по
которой член
последовательности вычисляется по k
предыдущим членам
.
Такая формула называется рекуррентным
соотношением или рекуррентным уравнением
порядка
.
Естественно, что при этом должны быть
известны (заданы) и начальные члены
.
Так,
формула
является рекуррентным соотношением
порядка 2. Положив, например,
,
получим рекуррентную последовательность
1, 2, 3, 5, 16, …
с начальными членами 1, 2.
Формула
– рекуррентное соотношение третьего
порядка.
Задача 1. Найти рекуррентное соотношение для чисел
.
Решение.
3. Решение рекуррентного соотношения
Пусть
рекуррентная последовательность k-го
порядка задана соотношением
.
Функция
,
называется решением рекуррентного
соотношения, если при подстановке
выражения
в это соотношение оно оказывается
справедливым для каждого
.
Чтобы
установить, является ли функция
решением рекуррентного соотношения
-го
порядка, приходится подставлять в это
соотношение и
,
...,
,
;
будем называть такой процесс алгоритмом
проверки решения.
Задача
2.
Доказать, что функция
является решением рекуррентного
соотношения
.
Решение.
Поскольку начальные члены рекуррентной последовательности можно задавать произвольно, то существует бесконечно много рекуррентных последовательностей, удовлетворяющих одному и тому же рекуррентному соотношению данного порядка.
Общим решением рекуррентного соотношения
-го
порядка называется выражение
.
Иными
словами, математическое выражение
является общим решением рекуррентного
соотношения
-го
порядка, когда выполняются следующие
условия:
1)
2)
На
основе понятия общего и частного решения
рекуррентного соотношения можно найти
способ описания всех рекуррентных
последовательностей, удовлетворяющих
заданному рекуррентному соотношению
-ого
порядка. Как следует из изложенного,
схема
нахождения любой такой последовательностей
такова:
1)
2)
3)
4)
Начальные
члены
последовательности будем называть
также начальными значениями (условиями)
частного решения, т.е. функции
.
К сожалению, не существует универсального способа решения рекуррентных соотношений, т.е. способа, пригодного в решении любого соотношения. Однако для некоторых частных видов соотношений такие способы найдены, например, для линейных рекуррентных соотношений.
Задача 3. Доказать, что последовательность
,
,
,
…,
,
…
квадратов натуральных чисел является однородной линейной рекуррентной последовательностью.
Решение.
Рассмотрим свойства решений однородного линейного рекуррентного соотношения k-го порядка.
Теорема
1. Пусть
– частное решения рекуррентного
соотношения (3) k-го
порядка,
– произвольное число. Тогда
– частное решение этого рекуррентного
соотношения.
Доказательство.
Теорема
2. Пусть
,
– частное решения рекуррентного
соотношения k-го
порядка (3). Тогда
– частное решение этого рекуррентного
соотношения.
Доказательство.
Теорема 3. Если
– корень алгебраического уравнения
,
(4)
то функция
является частным решением рекуррентного
соотношения
.
Доказательство.
Рассмотренные теоремы позволяют найти общее решение рекуррентного соотношения (3).
Теорема 4. Если характеристическое
уравнение (4) однородного линейного
рекуррентного соотношения (3) имеет
различных корней
,
то общее решение этого соотношения
имеет вид
.
Доказательство.
Задача 4. Найти общее решение
однородного линейного рекуррентного
соотношения
.
Решение.
Теорема 5. Пусть
характеристическое уравнение (4)
однородного линейного рекуррентного
соотношения (3) имеет только k-кратный
корень
.
Тогда общее решение рекуррентного
соотношения имеет вид
.