Як вирішити рекуррентное рівняння

Перед тим, як знайти формулу деякої математичної послідовності, необхідно знайти n-ий член цієї послідовності, виражений через попередні члени послідовності (а не як функція від n). Наприклад, було б непогано знати функцію для n-го члена послідовності Фібоначчі, але часто у вас є тільки рекуррентное рівняння, що зв`язує кожен член послідовності Фібоначчі з двома попередніми членами. Ця стаття розповість вам, як вирішити рекуррентное рівняння.

Метод 1 з 5: Арифметична прогресія

1
Розглянемо послідовність 5, 8, 11, 14, 17, 20,....
2
Кожен член цієї послідовності більше попереднього члена на 3, тому він може бути виражений рекурентним рівнянням, показаним на малюнку.
3
Рекурентне співвідношення виду a_n = A_n-1 + d є арифметичною прогресією.
4
Запишіть формулу для обчислення n-го члена арифметичної прогресії, як показано на малюнку.
5
Підставте у формулу значення даної вам послідовності. У нашому прикладі 5 - це 0-й член послідовності. Тоді формула має вигляд a_n = 5 + 3n. Якщо 5 - це 1-й член послідовності, то формула має вигляд a_n = 2 + 3n.

Метод 2 з 5: Геометрична прогресія

1
Розглянемо послідовність 3, 6, 12, 24, 48,....
2
Кожен член цієї послідовності більше попереднього члена в 2 рази, тому він може бути виражений рекурентним рівнянням, показаним на малюнку.
3
Рекурентне співвідношення виду a_n = R * a_n-1 є геометричною прогресією.
4
Запишіть формулу для обчислення n-го члена геометричної прогресії, як показано на малюнку.
5
Підставте у формулу значення даної вам послідовності. У нашому прикладі 3 - це 0-й член послідовності. Тоді формула має вигляд a_n = 3 * 2. Якщо 3 - це 1-й член послідовності, то формула має вигляд a_n = 3 * 2.

Метод 3 з 5: Многочлен

1
Розглянемо послідовність 5, 0, -8, -17, -25, -30,..., задану рекурентним рівнянням, показаним на малюнку.

2
Будь-яке рекурентне рівняння виду, показаного на малюнку (де р (n) - многчлен від n), має многочлен, показник якого на 1 більше, ніж показник р.
3
Напишіть многочлен відповідного порядку. У нашому прикладі p має другий порядок, тому необхідно написати кубічний многочлен, щоб представити послідовність a_n.
4
Так як в кубічному многочлене чотири невідомих коефіцієнта, запишіть систему з чотирьох рівнянь. Підійдуть будь-які чотири, тому розгляньте 0-ой, перший, 2-ий, 3-ий члени. Якщо хочете, розгляньте -1-ий член рекуррентного рівняння, щоб спростити процес рішення (але це не обов`язково).
5
Вирішіть отриману систему ступінь (р) +2 рівнянь для ступінь (р) = 2 невідомих так, як показано на малюнку.
6
Якщо a - це один із членів, використовуваних вами для обчислення коефіцієнтів, то ви швидко знайдете постійний член многочлена і зможете спростити систему до ступінь (р) +1 рівнянь для ступінь (р) +1 невідомих так, як показано на малюнку.
7
Вирішіть систему лінійних рівнянь і отримаєте c₃ = 1/3, c₂ = -5/2, C₁ = -17/6, C = 5. Запишіть формулу для a_n у вигляді многочлена з відомими коефіцієнтами.

Метод 4 з 5: Лінійні рекурентні рівняння

1
Це один з методів вирішення послідовності Фібоначчі. Однак цей метод можна застосовувати для вирішення будь-яких рекурентних рівнянь, в яких n-ий член є лінійною комбінацією попередніх k членів. Розглянемо послідовність 1, 4, 13, 46, 157, ....
2
Напишіть характеристичний многочлен рекуррентного рівняння. Для цього замініть a_n на x і розділіть на x- ви отримаєте багаточлен ступеня k і постійний член, відмінний від нуля.
3
Вирішіть характеристичний многочлен. У нашому прикладі він має ступінь 2, тому використовуйте формулу для знаходження коренів квадратного рівняння.
4
Будь-який вираз виду, показаного на малюнку, задовольняє рекурентному рівняння. c_i - це будь-які постійні, а підстави ступеня - це коріння характеристичного многочлена (вирішеного вище).
- Якщо характеристичний многочлен має кілька коренів, то потрібно зробити наступне. Якщо r - корінь кратності m, замість (c₁r) використовуйте (c₁r + c₂nr + c₃nr + ... + c_mnr). Наприклад, розглянемо послідовність 5, 0, -4, 16, 144, 640, 2240, ..., що задовольняє рекурентному рівняння a_n = 6a_n-1 - 12a_n-2 + 8a_n-3. Характеристичний многочлен має три корені, а формула записується так: a_n = 5 * 2 - 7 * n * 2 + 2 * n * 2.
5
Знайдіть постійну c_i, задовольняє початковим умовам. Для цього запишіть лінійну систему рівнянь з урахуванням початкових умов. Оскільки в нашому прикладі два невідомих, запишіть систему з двох рівнянь. Підійдуть будь-які два, тому розгляньте 0-ой і перші члени, щоб уникнути зведення ірраціонального числа в більшу ступінь.
6
Вирішіть отриману систему рівнянь.
7
Знайдені постійні підставте в формулу.

Метод 5 з 5: Виробляють функції

1
Розглянемо послідовність 2, 5, 14, 41, 122..., задану рекурентним рівнянням, показаним на малюнку. Воно не може бути вирішено за допомогою кожного з вищеописаних методів, але формула знаходиться через виробляють функції.
2
Напишіть виробляє функцію послідовності. Виробляє функція - це формальний степеневий ряд, де коефіцієнт при x є n-им членом послідовності.
3
Перетворіть виробляє функцію, як показано на малюнку. Метою цього кроку є знаходження рівняння, яке дозволить вам вирішити виробляє функцію А (х). Вийміть початковий член. Застосуйте рекуррентное рівняння для решти членів. Розбийте суму. Вийміть постійні члени. Використовуйте визначення А (х). Використовуйте формулу для обчислення суми геометричної прогресії.
4
Знайдіть виробляє функцію A (х).
5
Знайдіть коефіцієнт при x в А (х). Методи знаходження коефіцієнта залежать від виду функції А (х), але на малюнку показаний метод елементарних дробів у поєднанні з виробляє функцією геометричній прогресії.
6
Запишіть формулу для a_n, щоб знайти коефіцієнт при x в A (x).

Поради

Індуктивний метод теж дуже популярний. Найчастіше легко довести (використовуючи індуктивний метод), що деяка формула задовольняє деякому рекурентному рівняння, але проблема в тому, що потрібно заздалегідь вгадати формулу.
Деякі з описаних методів вимагають великого обсягу обчислень, що може спричинити помилки. Тому перевірте формулу по кільком відомим умовам.