Возвратные последовательности

Рекуррентным соотношением, рекуррентным уравнением или рекуррентной формулой называется соотношение вида a_n+k = F(n, a_n,a_n+1,...,a_n+k-1), которое позволяет вычислять все члены последовательности а₀,а₁,а₂, …, если заданы её первые k членов.

П р и м е р 5.6.1. 1. Формула а_{n+1 =} а_n + d задает арифметическую прогрессию.

2. Формула а_n+1 = q a_n определяет геометрическую прогрессию.

3. Формула а_{n+2 =} а_n+1 + а_n задает последовательность чисел Фибоначчи.

В случае, когда рекуррентное соотношение линейно и однородно, т.е. выполняется соотношение вида

а_n+k + p₁a_n+k-1 +... + p_ka_n = 0 (5.4)

(p = const), последовательность a₀,a₁,a₂,... называется возвратной. Многочлен

(5.5)

называется характеристическим для возвратной последовательности {а_n}. Корни многочлена Р_а(х) называются характеристическими.

Множество всех последовательностей, удовлетворяющих данному рекуррентному соотношению, называется общим решением.

Описание общего решения соотношения (5.4) имеет аналогию с описанием решения обыкновенного дифференциального уравнения с постоянными коэффициентами.

Теорема 5.6.1. 1. Пусть - корень характеристического многочлена (5.5). Тогда последовательность , где с – произвольная константа, удовлетворяет соотношению (5.4).

2. Если - простые корни характеристического многочлена (5.5), то общее решение рекуррентного соотношения (5.4) имеет вид , где с₁,с₂,…,с_k – произвольные константы.

3. Если - корень кратности r_i (i = 1,…,s) характеристического многочлена (5.5), то общее решение рекуррентного соотношения (5.4) имеет вид , где с_ij – произвольные константы.

Зная общее решение рекуррентного уравнения (5.4), по начальным условиям а₀,а₁,…,а_k можно найти неопределенные постоянные с_ij и тем самым получить решение уравнения (5.4) с данными начальными условиями.

П р и м е р 5.6.2. Найти последовательность {а_n}, удовлетворяющую рекуррентному соотношению и начальным условиям а₁=10, а₂=16.

Корнями характеристического многочлена Р_а(х) = х² - 4х + 3 являются числа х₁ = 1 и х₂ = 3. Следовательно, по теореме 5.6.1. общее решение имеет вид а_n = с₁ + с₂3ⁿ. Используя начальные условия, получаем систему

с₁ + 3с₂ = 10,

с₁ + 9с₂ = 16,

решая которую, находим с₁ = 7 и с₂ = 1. Таким образом, а_n = 7 + 3ⁿ.

Рассмотрим неоднородное линейное рекуррентное уравнение

(5.6)

Пусть {b_n} – общее решение однородного уравнения (5.4), а {с_n} – частное (конкретное) решение неоднородного уравнения (5.6). Тогда последовательность {b_n + с_n} образует общее решение уравнения (5.6), и тем самым справедлива.

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

Таким образом, в силу теоремы 5.6.1. задача нахождения общего решения рекуррентного уравнения (5.6) сводится к нахождению некоторого частного решения.

В отдельных случаях имеются общие рецепты нахождения частного решения.

Если (где не является характеристическим корнем), то, подставляя в (5.6), получаем и отсюда т.е. частное решение можно задать формулой

Пусть f(n) – многочлен степени r от переменной n, и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде Подставляя многочлены в формулу (5.6), получаем

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

П р и м е р 5.6.3. Найти решение уравнения

с начальным условием

Рассмотрим характеристический многочлен Р_а(х) = х + 2. Так как Р_а(х) = 3 0 и правая часть f(n) уравнения (5.6) равна n + 1, то частное решение будем искать в виде Подставляя с_n в уравнение (5.7), получаем = . Приравнивая коэффициенты в левой и правой частях последнего равенства, получаем систему

откуда находим Таким образом, частное решение уравнения (5.7) имеет вид По теореме 5.6.1. общее решение однородного уравнения задается формулой и по теореме 5.6.2. получаем общее решение уравнения (5.7): Из начального условия находим т.е. Таким образом,

Задачи и упражнения

1. Группе из пяти сотрудников выделено три путевки. Сколько существует способов распределения путевок, если:

а) все путевки различны; б) все путевки одинаковы?

2. Крокодил имеет 68 зубов. Доказать, что среди 16¹⁷ крокодилов может не оказаться двух с одним и тем же набором зубов.

3. Сколько различных десятизначных чисел можно написать, используя цифры 0,1 и 2?

4. Алфавит Х состоит из двух символов. Сколько существует слов алфавита Х, длины которых не превосходят 4?

5. Автомобильные номера данного региона состоят из трех цифр(всего 10 цифр) и трех букв алфавита ={A, B, C, D, E, H, K, M, O, P, T, X, Y}. Сколько автомобилей может быть занумеровано различными номерами?

6. Во взводе 3 сержанта и 30 солдат. Сколько существует способов выделения одного сержанта и трех солдат для патрулирования?

7. Сколько различных перестановок образуется из следующих слов:

а) зебра; б)баран; в)водород; г)абракадабра?

8. Сколько положительных чисел от 20 до 1000 делятся ровно на одно из чисел 7,11 и 13?

9. Найти решение уравнения с начальными условиями

10. Найти общее решение уравнения