2.4: Вирішення відносин повторення

Template:MathJaxLevin

Досліджуйте!

Розглянемо відношення повторення

\ begin {рівняння*} a_n = 5a_ {n-1} - 6a_ {n-2}. \ end {рівняння*}

1. Яку послідовність ви отримаєте, якщо початкові умови\(a_0 = 1\text{,}\)\(a_1 = 2\text{?}\) Дайте замкнуту формулу для цієї послідовності.
2. Яку послідовність ви отримаєте, якщо початкові умови\(a_0 = 1\text{,}\)\(a_1 = 3\text{?}\) Дайте замкнуту формулу.
3. Що робити, якщо\(a_0 = 2\) і\(a_1 = 5\text{?}\) знайти замкнуту формулу.

Ми бачили, що часто легше знайти рекурсивні визначення, ніж закриті формули. На щастя для нас, існує кілька методик перетворення рекурсивних визначень в закриті формули. Це називається вирішенням рецидивного відношення. Нагадаємо, що рекуррентне відношення є рекурсивним визначенням без початкових умов. Наприклад, рекуррентне відношення для послідовності Фібоначчі є\(F_n = F_{n-1} + F_{n-2}\text{.}\) (Це разом з початковими умовами\(F_0 = 0\) і\(F_1 = 1\) дає все рекурсивне визначення для послідовності.)

Приклад\(\PageIndex{1}\)

Знайти зв'язок повторення та початкові умови для\(1, 5, 17, 53, 161, 485\ldots\text{.}\)

Рішення

Знайти зв'язок повторення було б простіше, якби ми мали певний контекст для проблеми (наприклад, вежа Ханоя, наприклад). На жаль, у нас є тільки послідовність. Пам'ятайте, що відношення повторення говорить вам, як перейти від попередніх термінів до майбутніх термінів. Що тут відбувається? Ми могли б розглянути відмінності між термінами:\(4, 12, 36, 108, \ldots\text{.}\) Notice that these are growing by a factor of 3. Is the original sequence as well? \(1\cdot 3 = 3\text{,}\) \(5 \cdot 3 = 15\text{,}\) \(17 \cdot 3 = 51\) and so on. It appears that we always end up with 2 less than the next term. Aha!

Так\(a_n = 3a_{n-1} + 2\) is our recurrence relation and the initial condition is \(a_0 = 1\text{.}\)

Ми спробуємо вирішити ці рецидивні відносини. Під цим ми маємо на увазі щось дуже схоже на розв'язування диференціальних рівнянь: ми хочемо знайти функцію\(n\) (замкнуту формулу), яка задовольняє рекуррентному відношенню, а також початкову умову. ² Відносини повторення іноді називають різницевими рівняннями, оскільки вони можуть описувати різницю між термінами, і це підкреслює відношення до диференціальних рівнянь далі. Як і для диференціальних рівнянь, знайти рішення може бути складним завданням, але перевірити правильність рішення легко.

Приклад\(\PageIndex{2}\)

\(a_n = 2^n + 1\)Переконайтеся, що це рішення рекуррентного зв'язку\(a_n = 2a_{n-1} - 1\) з\(a_1 = 3\text{.}\)

Рішення

По-перше, легко перевірити початковий стан:\(a_1\) should be \(2^1 + 1\) according to our closed formula. Indeed, \(2^1 + 1 = 3\text{,}\) which is what we want. To check that our proposed solution satisfies the recurrence relation, try plugging it in.

\ почати {вирівнювати*} 2a_ {n-1} - 1\ ампер = 2 (2^ {n-1} + 1) - 1\\ ампер = 2^n + 2 - 1\\ ампер = 2^n +1\\ ампер = a_n.\ кінець {align*}

Ось що говорить наша рецидивна зв'язок! У нас є рішення.

Іноді ми можемо бути розумними і вирішити рецидивні відносини шляхом перевірки. Ми генеруємо послідовність, використовуючи відношення повторення і відстежуємо те, що ми робимо, щоб ми могли бачити, як перейти до пошуку тільки\(a_n\) термін. Ось два приклади того, як ви можете це зробити.

Телескопізація відноситься до явища, коли багато термінів у великій сумі скасовують - так сума «телескопів». Наприклад:

\ почати {рівняння*} (2 - 1) + (3 - 2) + (4 - 3) +\ cdots + (100 - 99) + (101 - 100) = -1 + 101\ кінець {рівняння*}

тому що кожен третій термін виглядає так:\(2 + -2 = 0\text{,}\) а потім\(3 + -3 = 0\) і так далі.

Ми можемо використовувати цю поведінку для вирішення рецидивних відносин. Ось приклад.

Приклад\(\PageIndex{3}\)

Вирішити зв'язок повторення\(a_n = a_{n-1} + n\) з початковим терміном\(a_0 = 4\text{.}\)

Рішення

Щоб відчути відношення повторення, випишіть перші кілька термінів послідовності:\(4, 5, 7, 10, 14, 19, \ldots\text{.}\) Look at the difference between terms. \(a_1 - a_0 = 1\) and \(a_2 - a_1 = 2\) and so on. The key thing here is that the difference between terms is \(n\text{.}\) We can write this explicitly: \(a_n - a_{n-1} = n\text{.}\) Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting \(a_{n-1}\) from both sides.

Тепер використовуйте це рівняння знову і знову, змінюючи\(n\) each time:

\ begin {align*} a_1 - a_0\ amp = 1\ a_2 - a_1\ ампер = 2\\ a_3 - a_2\ амп = 3\\ vdots\ quad\ ампер\ quad\ vdots\\ a_n - a_ {n-1}\ amp = п.\ кінець {align*}

Складіть всі ці рівняння разом. З правого боку отримуємо суму\(1 + 2 + 3 + \cdots + n\text{.}\) We already know this can be simplified to \(\frac{n(n+1)}{2}\text{.}\) What happens on the left-hand side? We get

\ begin {рівняння*} (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) +\ cdots (a_ {n-1} - a_ {n-2}) + (a_n - a_ {n-1}). \ end {рівняння*}

Це сума телескопів. Нам залишилося тільки\(-a_0\) from the first equation and the \(a_n\) from the last equation. Putting this all together we have \(-a_0 + a_n = \frac{n(n+1)}{2}\) or \(a_n = \frac{n(n+1)}{2} + a_0\text{.}\) But we know that \(a_0 = 4\text{.}\) So the solution to the recurrence relation, subject to the initial condition is

\ begin {рівняння*} a_n =\ frac {n (n+1)} {2} + 4. \ end {рівняння*}

(Тепер, коли ми це знаємо, ми повинні помітити, що послідовність є результатом додавання 4 до кожного з трикутних чисел.)

У наведеному вище прикладі показано спосіб розв'язання повторюваних відносин форми,\(a_n = a_{n-1} + f(n)\) де\(\sum_{k = 1}^n f(k)\) є відома замкнута формула. Якщо ви перепишіть відношення повторення,\(a_n - a_{n-1} = f(n)\text{,}\) а потім скласти всі різні рівняння з\(n\)\(n\text{,}\) діапазоном між 1 і лівою стороною завжди дасть вам\(a_n - a_0\text{.}\) Права сторона буде\(\sum_{k = 1}^n f(k)\text{,}\) саме тому нам потрібно знати закриту формулу для цієї суми.

Однак телескопізація не допоможе нам з рекурсією, наприклад,\(a_n = 3a_{n-1} + 2\) оскільки ліва сторона не буде телескопом. Ви будете мати\(-3a_{n-1}\), але тільки один\(a_{n-1}\text{.}\) Однак, ми все ще можемо бути розумними, якщо ми використовуємо ітерацію.

Ми вже бачили приклад ітерації, коли ми знайшли замкнуту формулу для арифметичних і геометричних послідовностей. Ідея полягає в тому, що ми повторюємо процес знаходження наступного члена, починаючи з відомого початкової умови, аж до тих пір, поки ми не маємо\(a_n\text{.}\) Потім ми спрощуємо. У прикладі арифметичної послідовності ми спростили\(d\) множенням на кількість разів, до яких ми додаємо,\(a\) коли ми отримуємо,\(a_n\text{,}\) щоб отримати від\(a_n = a + d + d + d + \cdots + d\) до\(a_n = a + dn\text{.}\)

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

Приклад\(\PageIndex{4}\)

Використовуйте ітерацію для вирішення рекуррентного відношення\(a_n = a_{n-1} + n\) з\(a_0 = 4\text{.}\)

Відповідь

Знову ж таки, почніть із записування відношення повторення, коли\(n = 1\text{.}\) This time, don't subtract the \(a_{n-1}\) terms to the other side:

\ begin {рівняння*} a_1 = a_0 + 1. \ end {рівняння*}

Зараз\(a_2 = a_1 + 2\text{,}\) but we know what \(a_1\) is. By substitution, we get

\ begin {рівняння*} a_2 = (a_0 + 1) + 2. \ end {рівняння*}

Тепер перейдіть до\(a_3 = a_2 + 3\text{,}\) using our known value of \(a_2\text{:}\)

\ begin {рівняння*} a_3 = ((a_0 + 1) + 2) + 3. \ end {рівняння*}

Помічаємо візерунок. Кожен раз беремо попередній термін і додаємо поточний індекс. Так

\ begin {рівняння*} a_n = ((((((a_0 + 1) +2) +3) +\ cdots + n-1) + n.\ end {рівняння*}

Перегрупуючи терміни, ми помічаємо, що\(a_n\) is just \(a_0\) plus the sum of the integers from \(1\) to \(n\text{.}\) So, since \(a_0 = 4\text{,}\)

\ begin {рівняння*} a_n = 4 +\ розрив {n (n+1)} {2}. \ end {рівняння*}

Звичайно, у цьому випадку нам ще потрібно було знати формулу для суми\(1,\ldots,n\text{.}\) Давайте спробуємо ітерацію з послідовністю, для якої телескопізація не працює.

Приклад\(\PageIndex{5}\)

Вирішити відношення повторення, що\(a_n = 3a_{n-1} + 2\) підлягає\(a_0 = 1\text{.}\)

Відповідь

Знову ж таки, ми повторюємо відношення повторення, будуючи до індексу\(n\text{.}\)

\ почати {вирівнювати*} a_1\ амп = 3a_0 + 2\ a_2\ amp = 3 (a_1) + 2 = 3 (3a_0 + 2) + 2\ a_3\ ампер = 3 [a_2] + 3 [3a_0 + 2) + 2] + 2\\ vdots\ ампер\ qquad\ vdots\\ a_n\ амп = 3 (a_ {n-1}) + 2 = 3 (3 (3\ cdots (3a_0 + 2) + 2) + 2)\ cdots + 2) + 2. \ end {вирівнювати*}

Важко побачити, що тут відбувається, тому що ми повинні розподілити всі ці 3. Давайте спробуємо ще раз, на цей раз трохи спрощуючи, як ми йдемо.

\ почати {вирівнювати*} a_1\ амп = 3a_0 + 2\ a_2\ амп = 3 (a_1) + 2 = 3 (3a_0 + 2) + 2 = 3^2a_0 + 2\ cdot 3\ amp = 3 [a_2] + 2 = 3 [3^2a_0 + 2\ cdot 3 + 2] + 2 = 3^3 + 2\ точка 3 ^ 2 + 2\ точка 3 + 2\\\ точки\ ампер\ квадратний\ квадратний\ vdots\ hspace {2in}\ vdots\ a_n\ amp = 3 (a_ {n-1}) + 2 = 3 (3^ {n-1} a_0 + 2\ крапка 3^ {n-2} +\ крапки +2) + 2\\ ампер\ квадратний\ квадрат = 3 ^ n a_0 + 2\ точка 3^ {n-1} + 2\ точка 3^ {n-2} +\ точки + 2\ точка 3 + 2. \ end {вирівнювати*}

Тепер спростимо. \(a_0 = 1\text{,}\) so we have \(3^n + \langle\text{stuff}\rangle\text{.}\) Note that all the other terms have a 2 in them. In fact, we have a geometric sum with first term \(2\) and common ratio \(3\text{.}\) We have seen how to simplify \(2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^{n-1}\text{.}\) We get \(\frac{2-2\cdot 3^n}{-2}\) which simplifies to \(3^n - 1\text{.}\) Putting this together with the first \(3^n\) term gives our closed formula:

\ begin {рівняння*} a_n = 2\ cdot 3^n - 1. \ end {рівняння*}

Ітерація може бути брудною, але коли відношення повторення стосується лише одного попереднього терміну (і, можливо, деякої функції\(n\)), воно може працювати добре. Однак спроба ітерації рекуррентних відносин, таких як,\(a_n = 2 a_{n-1} + 3 a_{n-2}\) буде занадто складною. Нам потрібно було б відстежувати два набори попередніх термінів, кожен з яких був виражений двома попередніми термінами і так далі. Довжина формули зростала б експоненціально (вдвічі кожен раз, насправді). На щастя, трапляється метод для вирішення рецидивних відносин, який дуже добре працює на таких стосунках.

Характерна методика коренів

Припустимо, ми хочемо вирішити рекуррентне відношення, виражене\(a_n = a_{n-1} + 6a_{n-2}\text{.}\) у вигляді комбінації двох попередніх термінів, таких як Іншими словами, ми хочемо знайти функцію,\(n\) яка задовольняє\(a_n - a_{n-1} - 6a_{n-2} = 0\text{.}\) Тепер ітерація занадто складна, але подумайте лише на секунду, що станеться, якби ми це зробили ітерація. На кожному кроці ми б, серед іншого, помножили попередню ітерацію на 6. Таким чином, наша закрита формула буде включати в себе\(6\) помножений деяку кількість разів. При цьому розумно здогадатися, що рішення буде містити деталі, які виглядають геометрично. Можливо, рішення прийме форму\(r^n\) для якоїсь постійної\(r\text{.}\)

Приємна річ у тому, що ми знаємо, як перевірити, чи є формула насправді рішенням рекуррентного відношення: підключіть його. Що станеться, якщо ми підключимо до рекурсії вище?\(r^n\) Отримуємо

\ begin {рівняння*} r^n - r^ {n-1} - 6r^ {n-2} = 0. \ end {рівняння*}

Тепер вирішуйте для\(r\text{:}\)

\ begin {рівняння*} r^ {n-2} (r^2 - r - 6) = 0,\ end {рівняння*}

так факторингом,\(r = -2\) або\(r = 3\) (або\(r = 0\text{,}\) хоча це нам не допомагає). Це говорить нам про те, що\(a_n = (-2)^n\) це рішення рецидивного відношення, як є\(a_n = 3^n\text{.}\) Який з них правильний? Вони обидва є, якщо ми не вкажемо початкові умови. Зверніть увагу, що ми могли б також мати\(a_n = (-2)^n + 3^n\text{.}\) Або\(a_n = 7(-2)^n + 4\cdot 3^n\text{.}\) Насправді, для будь-якого\(a\) і\(b\text{,}\)\(a_n = a(-2)^n + b 3^n\) є рішенням (спробуйте підключити це до повторення відносини). Щоб знайти значення\(a\) і\(b\text{,}\) використовувати початкові умови.

Це вказує нам в сторону більш загальної методики вирішення рецидивних відносин. Зверніть увагу, що ми завжди зможемо врахувати те,\(r^{n-2}\) як ми зробили вище. Так що ми дійсно піклуємося тільки про іншу частину. Ми називаємо цю іншу частину характеристичним рівнянням для рекуррентного відношення. Нас цікавить пошук коренів характерного рівняння, які називаються (дивують) характерними коренями.

характерні коріння

З урахуванням\(a_n + \alpha a_{n-1} + \beta a_{n-2} = 0\text{,}\) рецидивного відношення характерний многочлен дорівнює

\ begin {рівняння*} x^2 +\ альфа х +\ бета\ кінець {рівняння*}

даючи характеристичне рівняння:

\ begin {рівняння*} x^2 +\ альфа х +\ бета = 0. \ end {рівняння*}

Якщо\(r_1\) і\(r_2\) є двома чіткими коренями характеристичного многочлена (тобто розв'язків характеристичного рівняння), то розв'язком рекуррентного відношення є

\ begin {рівняння*} a_n = ar_1^n + br_2^n,\ end {рівняння*}

де\(a\) і\(b\) є константами, визначеними початковими умовами.

Приклад\(\PageIndex{6}\)

Вирішити зв'язок повторення\(a_n = 7a_{n-1} - 10 a_{n-2}\) з\(a_0 = 2\) і\(a_1 = 3\text{.}\)

Рішення

Перепишіть відношення повторення\(a_n - 7a_{n-1} + 10a_{n-2} = 0\text{.}\) Now form the characteristic equation:

\ begin {рівняння*} x^2 - 7x + 10 = 0\ end {рівняння*}

і вирішити для\(x\text{:}\)

\ begin {рівняння*} (x - 2) (x - 5) = 0\ end {рівняння*}

так\(x = 2\) and \(x = 5\) are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form

\ begin {рівняння*} a_n = a 2^n + b 5^n.\ end {рівняння*}

Знайти\(a\) and \(b\text{,}\) plug in \(n =0\) and \(n = 1\) to get a system of two equations with two unknowns:

\ почати {вирівнювати*} 2\ ампер = a 2^0 + b 5^0 = a + б\\ 3\ ампер = a 2^1 + b 5^1 = 2a + 5b\ кінець {вирівнювати*}

Рішення цієї системи дає\(a = \frac{7}{3}\) and \(b = -\frac{1}{3}\) so the solution to the recurrence relation is

\ begin {рівняння*} a_n =\ frac {7} {3} 2^n -\ frac {1} {3} 5^n.\ end {рівняння*}

Мабуть, найвідомішим рецидивним відношенням є те,\(F_n = F_{n-1} + F_{n-2}\text{,}\) що разом з початковими умовами\(F_0 = 0\) і\(F_1= 1\) визначає послідовність Фібоначчі. Але зверніть увагу, що це саме той тип рецидивного відношення, на якому ми можемо використовувати характерну кореневу техніку. Коли ви це робите, єдине, що змінюється, це те, що характеристичне рівняння не коефіцієнт, тому вам потрібно використовувати квадратичну формулу, щоб знайти характерні корені. По суті, це дає третє найвідоміше ірраціональне число,\(\varphi\text{,}\) золоте співвідношення.

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

Однак характерний многочлен може мати лише один корінь. Це може статися, якщо характерні поліноміальні фактори як\((x - r)^2\text{.}\) Це все ще так, що\(r^n\) було б розв'язком рецидивного відношення, але ми не зможемо знайти розв'язки для всіх початкових умов, використовуючи загальну форму,\(a_n = ar_1^n + br_2^n\text{,}\) оскільки ми не можемо розрізнити\(r_1^n\) і \(r_2^n\text{.}\)Нам пощастило, хоча:

Характерна методика коренів для повторних коренів

Припустимо, що відношення рецидиву\(a_n = \alpha a_{n-1} + \beta a_{n-2}\) має характерний многочлен лише з одним коренем.\(r\text{.}\) Тоді розв'язком рецидивного відношення є

\ begin {рівняння*} a_n = ar^n + bnr^n\ end {рівняння*}

де\(a\) і\(b\) є константами, визначеними початковими умовами.

Зверніть увагу на\(bnr^n\text{.}\) зайве\(n\) в Це дозволяє нам вирішувати для констант\(a\) і\(b\) з початкових умов.

Приклад\(\PageIndex{7}\)

Вирішити зв'язок повторення\(a_n = 6a_{n-1} - 9a_{n-2}\) з початковими умовами\(a_0 = 1\) та\(a_1 = 4\text{.}\)

Відповідь

Характерний многочлен - це\(x^2 - 6x + 9\text{.}\) We solve the characteristic equation

\ begin {рівняння*} x^2 - 6x + 9 = 0\ end {рівняння*}

шляхом факторингу:

\ begin {рівняння*} (x - 3) ^2 = 0\ end {рівняння*}

так\(x =3\) is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form

\ begin {рівняння*} a_n = a 3^n + bn3^n\ end {рівняння*}

для деяких констант\(a\) and \(b\text{.}\) Now use the initial conditions:

\ почати {вирівнювати*} a_0 = 1\ амп = a 3^0 + б\ cdot 0\ cdot 3^0 = a\\ a_1 = 4\ ампер = a\ cdot 3 + b\ cdot 1\ cdot3 = 3a + 3b. \ end {вирівнювати*}

Так як\(a = 1\text{,}\) we find that \(b = \frac{1}{3}\text{.}\) Therefore the solution to the recurrence relation is

\ begin {рівняння*} a_n = 3^n +\ frac {1} {3} n3^n.\ end {рівняння*}

Хоча ми не будемо розглядати приклади складніші, ніж ці, цю характерну кореневу техніку можна застосувати до набагато складніших рецидивних відносин. Наприклад,\(a_n = 2a_{n-1} + a_{n-2} - 3a_{n-3}\) має характерний многочлен\(x^3 - 2 x^2 - x + 3\text{.}\) Припускаючи, що ви бачите, як множити такий поліном ступеня 3 (або більше), ви можете легко знайти характерні корені і як таке вирішити відношення повторення (рішення виглядало б,\(a_n = ar_1^n + br_2^n + cr_3^n\) якби було 3 чітких коренів). Також можна вирішити рецидивні відносини виду\(a_n = \alpha a_{n-1} + \beta a_{n-2} + C\) для деякої константи Також\(C\text{.}\) можливо (і прийнятно) для характерних коренів бути комплексними числами.