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

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

кроки

Метод 1 з 5:

Арифметична прогресія

1. Розглянемо послідовність 5, 8, 11, 14, 17, 20, ....

Зображення з назвою Solve Recurrence Relations Step 2

2. Кожен член цієї послідовності більше попереднього члена на 3, тому він може бути виражений рекурентним рівнянням, показаним на малюнку.

Зображення з назвою Solve Recurrence Relations Step 3

3. Рекурентне співвідношення виду a_н = a_n-1 + d є арифметичною прогресією.

Зображення з назвою Solve Recurrence Relations Step 4

4. Запишіть формулу для обчислення n-го члена арифметичної прогресії, як показано на малюнку.

Зображення з назвою Solve Recurrence Relations Step 5

5. Підставте у формулу значення даної вам послідовності. У нашому прикладі 5 - це 0-й член послідовності. Тоді формула має вигляд a_н = 5 + 3n. Якщо 5 - це 1-й член послідовності, то формула має вигляд a_н = 2 + 3n.

Метод 2 з 5:

Геометрична прогресія

1. Розглянемо послідовність 3, 6, 12, 24, 48, ....

Зображення з назвою Solve Recurrence Relations Step 7

2. Кожен член цієї послідовності більше попереднього члена в 2 рази, тому він може бути виражений рекурентним рівнянням, показаним на малюнку.

Зображення з назвою Solve Recurrence Relations Step 8

3. Рекурентне співвідношення виду a_н = R * a_n-1 є геометричною прогресією.

4. Запишіть формулу для обчислення n-го члена геометричної прогресії, як показано на малюнку.

Зображення з назвою Solve Recurrence Relations Step 10

5. Підставте у формулу значення даної вам послідовності. У нашому прикладі 3 - це 0-й член послідовності. Тоді формула має вигляд a_н = 3 * 2. Якщо 3 - це 1-й член послідовності, то формула має вигляд a_н = 3 * 2.

Метод 3 з 5:

многочлен

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

Зображення з назвою Solve Recurrence Relations Step 12

2. Будь-яке рекурентне співвідношення виду, показаного на малюнку (де р (n) - многчлен від n), має многочлен, показник якого на 1 більше, ніж показник р.

Зображення з назвою Solve Recurrence Relations Step 13

3. Напишіть многочлен відповідного порядку. У нашому прикладі p має другий порядок, тому необхідно написати кубічний многочлен, щоб представити послідовність a_н.

Зображення з назвою Solve Recurrence Relations Step 14

4. Так як в кубічному многочлене чотири невідомих коефіцієнта, запишіть систему з чотирьох рівнянь. Підійдуть будь-які чотири, тому розгляньте 0-ой, 1-ий, 2-ий, 3-ий члени. Якщо хочете, розгляньте -1-ий член рекуррентного рівняння, щоб спростити процес рішення (але це не обов`язково).

Зображення з назвою Solve Recurrence Relations Step 15

5. Вирішіть отриману систему ступінь (р) +2 рівнянь для ступінь (р) = 2 невідомих так, як показано на малюнку.

Зображення з назвою Solve Recurrence Relations Step 16

6. якщо a - це один з членів, які використовуються вами для обчислення коефіцієнтів, то ви швидко знайдете постійний член многочлена і зможете спростити систему до ступінь (р) +1 рівнянь для ступінь (р) +1 невідомих так, як показано на малюнку.

Зображення з назвою Solve Recurrence Relations Step 17

7. Вирішіть систему лінійних рівнянь і отримаєте c₃ = 1/3, c₂ = -5/2, c₁ = -17/6, c = 5. Запишіть формулу для a_н у вигляді многочлена з відомими коефіцієнтами.

Метод 4 з 5:

Лінійні рекурентні рівняння

1. Це один з методів вирішення послідовності Фібоначчі. Однак цей метод можна застосовувати для вирішення будь-яких зворотних рівнянь, в яких n-ий член є лінійною комбінацією попередніх k членів. Розглянемо послідовність 1, 4, 13, 46, 157, ....

Зображення з назвою Solve Recurrence Relations Step 19

2. Напишіть характеристичний многочлен рекуррентного рівняння. Для цього замініть a_нна x і розділіть наx- ви отримаєте многочлен ступеня k і постійний член, відмінний від нуля.

Зображення з назвою Solve Recurrence Relations Step 20

3. Вирішіть характеристичний многочлен. У нашому прикладі він має ступінь 2, тому використовуйте формулу для знаходження коренів квадратного рівняння.

Зображення з назвою Solve Recurrence Relations Step 21

4. Будь-яке вираження виду, показаного на малюнку, задовольняє рекурентного рівняння. з_і- це будь-які постійні, а підстави ступеня - це коріння характеристичного многочлена (вирішеного вище).

Якщо характеристичний многочлен має кілька коренів, то потрібно зробити наступне. Якщо r - корінь кратності m, замість (c₁r) використовуйте (c₁r + c₂nr + c₃нр + ... + з_мnr). Наприклад, розглянемо послідовність 5, 0, -4, 16, 144, 640, 2240, ..., задовольняє рекурентного рівняння a_н = ша_n-1 - 12a_n-2 + 8а_n-3. Характеристичний многочлен має три кореня, а формула записується так: a_н = 5 * 2 - 7 * n * 2 + 2 * n * 2.

Зображення з назвою Solve Recurrence Relations Step 22

5. Знайдіть постійну c_i, задовольняє початковим умовам. Для цього запішітелінейную систему рівнянь з урахуванням початкових умов. Оскільки в нашому прімередва невідомих, запишіть систему з двох рівнянь. Підійдуть будь-які два, тому розгляньте 0-ой і 1-ий члени, щоб уникнути зведення ірраціонального числа в більшу ступінь.

Зображення з назвою Solve Recurrence Relations Step 23

6. Вирішіть отриману систему рівнянь.

Зображення з назвою Solve Recurrence Relations Step 24

7. Знайдені постійні підставте в формулу.

Метод 5 з 5:

виробляють функції

1. Розглянемо послідовність 2, 5, 14, 41, 122 ..., задану рекурентним рівнянням, показаним на малюнку. Воно не може бути вирішено за допомогою будь-якого з вищеописаних методів, але формула знаходиться через що виробляють функції.

Зображення з назвою Solve Recurrence Relations Step 26

2. Напишіть виробляє функцію послідовності. Виробляє функція це формальний статечної ряд, де коефіцієнт при x є n-им членом послідовності.

Зображення з назвою Solve Recurrence Relations Step 27

3. Перетворіть виробляє функцію, як показано на малюнку. Метою цього кроку є знаходження рівняння, яке дозволить вам вирішити виробляє функцію А (х). Вийміть початковий член. Застосуйте рекурентне співвідношення для решти членів. розбийте суму. Вийміть постійні члени. Використовуйте визначення А (х). Використовуйте формулу для обчислення суми геометричної прогресії.

Зображення з назвою Solve Recurrence Relations Step 28

4. Знайдіть виробляє функцію A (х).

Зображення з назвою Solve Recurrence Relations Step 29

5. Знайдіть коефіцієнт при x в А (х). Методи знаходження коефіцієнта залежать від виду функції А (х), але на малюнку показаний метод елементарних дробів в поєднанні з виробляє функцією геометричній прогресії.

Зображення з назвою Solve Recurrence Relations Step 30

6. Запишіть формулу для a_н, щоб знайти коефіцієнт при x в A (x).

Поради

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