Электронная библиотека
Рассмотрим обобщение последовательностей Фибоначчи. Формула
называется однородным линейным рекуррентным уравнением порядка r. Ее решением является последовательность <un>, однозначно определенная начальными значениями u0, u1, u2, …∙, ur –1. Решение такого уравнения называется возвратной, или рекуррентной последовательностью порядка r.
Геометрическая прогрессия является решением уравнения un+1 = qun. Ее члены описываются формулой un = u0q n . Отсюда геометрическая прогрессия является возвратной последовательностью порядка 1.
Арифметическая прогрессия un = u0 + nd удовлетворяет соотношению:
Получаем однородное рекуррентное уравнение:
Начальные данные задаются значениями u0 и u1 = u0 + d. Отсюда, арифметическая прогрессия является возвратной последовательностью порядка 2.
Произвольная периодическая последовательность является возвратной последовательностью порядка p, удовлетворяющей рекуррентному соотношению:
Здесь p – период последовательности.
Для заданного рекуррентного уравнения
найдем производящую функцию возвратной последовательности <un>.
Произведение u(x)K(x) = D(x) является многочленом степени, меньшей r.
Вычислим коэффициент ряда D(x) при x n + r . Он при n ≥ 0 будет равен:
Отсюда D(x) – многочлен степени, меньшей чем n.
Частное от деления любых двух многочленов является производящей функцией некоторой возвратной последовательности, порядок которой равен степени знаменателя.
Применим доказанную теорему к решению рекуррентного уравнения
при начальных условиях u0 = u1 = 1.
Здесь K(x) = 1 — 5x + 6x 2 .
По теореме 1 коэффициенты при x 2 , x 3 … равны нулю, а u0 = u1 = 1. Следова
Следующий шаг – разложение знаменателя K(x) в произведение
В данном случае это можно сделать с помощью формулы Виеты. Поскольку имеют место равенства:
то числа a1 и a2 будут корнями квадратного уравнения a 2 — 5a +6 = 0. Решая это квадратное уравнение, получаем:
Приходим к формуле
Теперь найдем разложение в сумму простых дробей методом неопределенных коэффициентов:
Получим систему линейных уравнений:
имеющую решение A = 2, B = -1. Отсюда
Это приводит к ответу
В общем случае числа aI в разложении
являются корнями уравнения:
ибо K(x) = . Это уравнение F(a) = 0 называется характеристическим.
Если все корни уравнения F(a)=0 действительны и различны, то получаем:
Это позволяет составить систему линейных уравнений для нахождения Ai с помощью известных значений u0, u1, …∙, ur-1.
Рассмотрим рекуррентное уравнение:
Составим характеристическое уравнение:
Его корни a 1 = 2, a 2 = —1 не равны между собой и являются вещественными числами. Поэтому решение рекуррентного уравнения можно искать в виде:
Значения un известны при n = 0, 1, откуда получаем систему линейных уравнений для нахождения коэффициентов A1, A2:
Решаем эту систему уравнений:
получаем A1 = A2 = 1. Приходим к следующему ответу:
Если существуют кратные корни, то, пользуясь формулами для производных от геометрической прогрессии, можно доказать, что решение будет дополняться слагаемыми:
где k – кратность корня .
Решим рекуррентное уравнение:
С этой целью составим характеристическое уравнение:
Оно имеет кратные корни a 1 = a 2 =3. Поэтому решение рекуррентного уравнения нужно искать в виде
Подставляя известные значения u0 = 1 и u1 = 6, приходим к системе уравнений
Она имеет решение A1 = A2 = 1. Получаем ответ:
Свойства производящих функций
1. Сколько делителей, включая само число и 1, имеет число 720?
2. Доказать, что при n > 0 имеют место соотношения:
3. Найти производящую функцию последовательности an = 10ncos(2n).
4. Найти производящую функцию последовательности an = 10 n sin(2n).
5. Найти производящую функцию последовательности an = 10 n n.
6. Найти производящую функцию последовательности an = 10 n n.
7. Найти производящую функцию последовательности an = 10 n n(n+1).
8. Найти производящую функцию последовательности an = 10 n n 2 .
9. Найти производящую функцию последовательности an = 10 n /(n+1).
10. Найти производящую функцию последовательности an = 10 n /(n+1)(n+2).
11. Доказать рекуррентное соотношение для производящих функций последовательностей n k :
12. Найти производящие функции последовательностей an = n k , при k = 1, 2, 3, 4.
Рекуррентные соотношения и уравнения
В этом разделе вы найдете бесплатные примеры решений рекуррентных соотношений методом характеристического уравнения и подбора частного решения по правой части. Также приведены краткие алгоритмы решения для двух методов и пример их использования для последовательности Фибоначчи.
Как решать рекуррентные соотношения?
Для решения рекуррентных соотношений применяют один из двух основных способов:
- Метод производящих функций
- Метод характеристического уравнения
В следующем разделе мы сравним, как выглядит процесс решения для одной и той же последовательности двумя методами.
Метод производящих функций
- Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_
= …, \\ … \\ a_ = …, n\geqslant k$$ - Домножить каждую строчку на $z$ в соответствующей степени $z^
\cdot a_ $ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_ ^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$. - Решить полученное уравнение относительно $G(z)$.
- Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.
Метод характеристических функций
Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:
- Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_
a_ + p_ a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_ a_ + . + p_n a_n =0. $$ - Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_
\lambda^ + p_ \lambda^ + . + p_ \lambda + p_n =0. $$ - Выписать согласно полученным корням $\lambda_1, . \lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +. +C_k \lambda_k^n \, \mbox < для случая различных простых корней>, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +. +C_m n^m \lambda_1^n+. +C_k \lambda_k^n \mbox < для случая корня >\, \lambda_1 \, < кратности >\, m. $$
- Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
- Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
- Подставить начальные условия $a_0, a_1, . a_
$ и получить значения констант $C_1, . C_k$.
Решение для последовательности чисел Фибоначчи
Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:
$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$
Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.
Общая формула данной рекуррентной последовательности имеет вид6
Способ 1. Производящяя функция
Начинаем с второго шага алгоритма, домножаем на $z^n$:
$$\begin
Складываем все строчки:
На третьем шаге алгоритма приводим все суммы к замкнутому виду:
откуда выводим искомое выражение для производящей функции:
Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:
Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:
Аналогично (но с делением на $z_2$) действуем со второй дробью:
Преобразуем данное выражение, используя то, что
$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt <5>$$ $$f_n=\frac<1><\sqrt<5>>\left( \biggl( \frac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \frac<1-\sqrt<5>> <2>\biggr)^n \right). $$
Способ 2. Характеристическое уравнение
Запишем характеристический многочлен для $f_n=f_
Тогда общее решение однородного рекуррентного уравнения имеет вид:
Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.
Решая систему, найдем
Итоговое выражение для последовательности чисел Фибоначчи:
Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.
Примеры решений
Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку
Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку
Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.
Задача 4. Найти последовательность $
Дискретная математика — рекуррентное соотношение
В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.
Определение
Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая F n как некоторую комбинацию F i с i n ).
Пример — ряд Фибоначчи — F n = F n − 1 + F n − 2 , Ханойская башня — F n = 2 F n − 1 + 1
Линейные рекуррентные отношения
Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате x n = A 1 x n − 1 + A 2 x n − 1 + A 3 x n − 1 + d o t s A k x n k ( A n — константа, а A k n e q 0 ) на последовательности чисел как полинома первой степени.
Вот некоторые примеры линейных рекуррентных уравнений —
Рецидив отношений | Начальные значения | Решения |
---|---|---|
F n = F n-1 + F n-2 | a 1 = a 2 = 1 | Число Фибоначчи |
F n = F n-1 + F n-2 | а 1 = 1, а 2 = 3 | Номер Лукаса |
F n = F n-2 + F n-3 | a 1 = a 2 = a 3 = 1 | Падовская последовательность |
F n = 2F n-1 + F n-2 | a 1 = 0, a 2 = 1 | Число Пелла |
Как решить линейное рекуррентное соотношение
Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — F n = A F n − 1 + B F n − 2 , где A и B — действительные числа.
Характеристическое уравнение для вышеуказанного рекуррентного соотношения —
x 2 − A x e − B = 0
Три случая могут возникнуть при поиске корней —
Случай 1 — Если это уравнение учитывается как ( x − x 1 ) ( x − x 1 ) = 0 и оно дает два различных реальных корня x 1 и x 2 , то F n = a x n 1 + b x n 2 является решение. [Здесь a и b являются константами]
Случай 2 — Если это уравнение вычисляется как ( x − x 1 ) 2 = 0 , и оно порождает один действительный корень x 1 , то решением является F n = a x n 1 + b n x n 1 .
Случай 3 — Если уравнение дает два различных комплексных корня, x 1 и x 2 в полярной форме x 1 = r a n g l e t h e t a и x 2 = r a n g l e ( − t h e t a ) , то F n = r n ( a c o s ( n t h e t a ) + b s i n ( n t h e t a ) ) является решением.
Решите рекуррентное соотношение F n = 5 F n − 1 − 6 F n − 2 , где F 0 = 1 и F 1 = 4 .
Характеристическое уравнение рекуррентного соотношения —
Итак, ( x − 3 ) ( x − 2 ) = 0
x 1 = 3 и x 2 = 2
Корни реальны и различны. Итак, это в форме дела 1
F n = a x n 1 + b x n 2
Здесь F n = a 3 n + b 2 n ( A s x 1 = 3 a n d x 2 = 2 )
1 = F 0 = a 3 0 + b 2 0 = a + b
4 = F 1 = a 3 1 + b 2 1 = 3 a + 2 b
Решая эти два уравнения, мы получаем a = 2 и b = − 1
Следовательно, окончательное решение —
$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$
Решите рекуррентное соотношение — F n = 10 F n − 1 − 25 F n − 2 , где F 0 = 3 и F 1 = 17 .
Характеристическое уравнение рекуррентного соотношения —
x 2 − 10 x − 25 = 0
Итак, ( x − 5 ) 2 = 0
Следовательно, существует один действительный корень x 1 = 5
Поскольку существует единый действительный корень, он имеет вид случая 2
F n = a x n 1 + b n x n 1
3 = F 0 = a .5 0 + b .0 .5 0 = a
17 = F 1 = a .5 1 + b .1 .5 1 = 5 a + 5 b
Решая эти два уравнения, мы получаем a = 3 и b = 2 / 5
Следовательно, окончательное решение — F n = 3.5 n + ( 2 / 5 ) . n .2 n
Решите рекуррентное соотношение F n = 2 F n − 1 − 2 F n − 2 , где F 0 = 1 и F 1 = 3
Характеристическое уравнение рекуррентного соотношения —
http://www.matburo.ru/ex_dm.php?p1=dmrekur
http://coderlessons.com/tutorials/akademicheskii/diskretnaia-matematika/diskretnaia-matematika-rekurrentnoe-sootnoshenie