13. Рекуррентные соотношения |
Рассмотрим последовательность элементов Всякую конечную последовательность элементов можно рассматривать как бесконечную, считая все её элементы, начиная с некоторого номера, равными нулю. Определение. Рекуррентным соотношением между элементами последовательности Например, рекуррентное соотношение Для вычисления любого элемента последовательности с помощью заданного рекуррентного соотношения требуется вычисление всех предыдущих её элементов. Если заданная последовательность элементов удовлетворяет линейному рекуррентному соотношению, то решение задачи об отыскании общей формулы вычисления Рассмотрим последовательность элементов
Тогда (2) – линейное однородное рекуррентное соотношение, соответствующее (1):
Определение. Характеристическим Уравнением, соответствующим (2), называется уравнение вида
Корни уравнения (3) Теорема 13.1. (О структуре общего решения линейного неоднородного рекуррентного соотношения (1)). Пусть Теорема 13.2. (О структуре общего решения линейного однородного рекуррентного соотношения (2)). Если Общее решение рекуррентного соотношения (2) при
Пример. Выведем формулу Бине для вычисления последовательности чисел Фибоначчи. Решение.
Составим характеристическое уравнение Решением системы является пара чисел Полученная формула называется формулой Бине и применяется для вычисления значений последовательности Фибоначчи только по их номеру, независимо от предыдущих членов последовательности. Замечание. Часто рассматривается последовательность Например, для последовательности чисел Фибоначчи 0, 1, 1, 2, 3, 5, … рекуррентное соотношение записывается в виде Задачи и упражнения. 13.1. Найдите формулу общего члена последовательности чисел, заданной рекуррентным соотношением 13.2. Найдите формулу общего члена последовательности чисел, заданной рекуррентным соотношением 13.3. Составьте рекуррентное соотношение последовательности квадратов натуральных чисел. 14. Понятие производящей функции. Рассмотрим последовательность чисел
Рассмотрим также последовательность функций действительной или комплексной переменной
Формально составим функциональный ряд, используя элементы (1) и (2): Будем считать ряд (3) сходящимся абсолютно на Определение. Сумма Чаще других используются степенные функции Например. Положим в формуле бинома Ньютона
Пример. Составить производящую функцию последовательности чисел Фибоначчи Решение. Используем последовательность функций действительной переменной
По допущению все ряды абсолютно сходятся на R.
Подставив суммы в (4), получим Задачи и упражнения. 14.1. Докажите, что функция 14.2. Найдите производящую функцию для последовательности чисел 14.3. Найдите общий член 14.4. Найдите общий член
|