Если член последовательности зависит от двух предыдущих: xn=pxn−1+qxn−2, — ищем решения в виде геометрической прогрессии xn=λn. Подстановка даёт характеристическое уравнение λ2−pλ−q=0. Если у него два разных вещественных корня λ1=λ2, то подходит любая комбинация c1λ1n+c2λ2n, а числа c1,c2 подбираются по первым двум членам.
Что пригодится из прошлого: рекуррентные соотношения первого порядка — мысль «решить соотношение значит найти формулу для xn»; квадратные уравнения и дискриминант — из школьной алгебры. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача
Найти общий член последовательности, заданной условиями
xn=p⋅xn−1+q⋅xn−2,x0=a, x1=b,n=2,3,…(4)
где p,q,a,b — заданные числа. Такое соотношение называется линейным (неизвестные члены входят только в первой степени), однородным (нет лишней добавки), второго порядка (член зависит от двух предыдущих), с постоянными коэффициентами (p,q не меняются).
Нужны два начальных значения, x0 и x1: без них первые члены неизвестны, а каждый следующий получается из двух предыдущих.
Пример. xn=5xn−1−6xn−2, x0=0, x1=1: получаем x2=5⋅1−6⋅0=5, x3=5⋅5−6⋅1=19, x4=5⋅19−6⋅5=65, … Есть ли для этого общая формула?
Догадка: искать геометрическую прогрессию
Самая простая последовательность, у которой каждый член получается умножением на одно и то же число, — геометрическая прогрессия xn=λn (λ=0). Проверим, при каком λ она подходит. Подставим в xn=pxn−1+qxn−2:
λn=pλn−1+qλn−2.
Разделим на λn−2=0:
λ2−pλ−q=0.
Это характеристическое уравнение соотношения (4). Его дискриминант D=p2+4q (так как в уравнении λ2−pλ−q=0 свободный член равен −q). Возможны три случая:
- D>0: два разных вещественных корня — разберём в этой главе;
- D=0: один корень (кратный);
- D<0: два комплексных корня.
Два последних случая — в следующей главе.
Принцип суперпозиции
Пусть последовательности un и vn удовлетворяют соотношению (4), то есть un=pun−1+qun−2 и vn=pvn−1+qvn−2. Тогда для любых чисел c1,c2 последовательность c1un+c2vn тоже удовлетворяет (4):
c1un+c2vn=p(c1un−1+c2vn−1)+q(c1un−2+c2vn−2).
Умножьте первое равенство на c1, второе на c2 и сложите — получится именно это. То есть решения можно складывать и умножать на числа.
Случай D>0: два вещественных корня
Пусть характеристическое уравнение имеет два разных вещественных корня λ1=λ2 (D=p2+4q>0). Тогда для любых вещественных c1,c2 последовательности c1λ1n и c2λ2n удовлетворяют (4), а значит, и их сумма
xn=c1λ1n+c2λ2n.
Подбор констант. Подставим n=0 и n=1 в эту формулу и потребуем x0=a, x1=b:
{a=x0=c1+c2,b=x1=c1λ1+c2λ2.
Умножим первое уравнение на λ1 и вычтем из второго: b−λ1a=c2(λ2−λ1). Значит,
c2=λ2−λ1b−λ1a,c1=a−c2=λ2−λ1λ2a−b.
(Деление возможно, потому что λ2=λ1.) Итого
xn=λ2−λ1λ2a−bλ1n+λ2−λ1b−λ1aλ2n(5)
— решение соотношения (4) в случае D=p2+4q>0. Если поменять корни местами (λ1↔λ2), получится та же последовательность.
Замечание. Если q=0, один из корней равен нулю (λ2−pλ=λ(λ−p)). Формула (5) остаётся верной, если считать 00=1 (это нужно при n=0).
Почему это единственное решение. Последовательность однозначно определена парой x0,x1: по ним находится x2, затем x3 и так далее. Формула (5) удовлетворяет и соотношению, и обоим начальным условиям, значит, совпадает с искомой последовательностью.
Примеры
1. xn=5xn−1−6xn−2, x0=0, x1=1. Характеристическое уравнение λ2−5λ+6=0, корни λ1=2, λ2=3 (D=25−24=1>0). По формуле (5):
c1=3−23⋅0−1=−1,c2=3−21−2⋅0=1,xn=3n−2n.
| n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| xn по правилу |
0 |
1 |
5 |
19 |
65 |
211 |
665 |
2059 |
| 3n−2n |
0 |
1 |
5 |
19 |
65 |
211 |
665 |
2059 |
2. xn=xn−1+2xn−2, x0=1, x1=1. Уравнение λ2−λ−2=0, D=1+8=9, корни λ1=−1, λ2=2. Константы:
c1=2−(−1)2⋅1−1=31,c2=31−(−1)⋅1=32,
поэтому
xn=31(−1)n+322n=32n+1+(−1)n.
| n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| xn по правилу |
1 |
1 |
3 |
5 |
11 |
21 |
43 |
85 |
171 |
| 32n+1+(−1)n |
1 |
1 |
3 |
5 |
11 |
21 |
43 |
85 |
171 |
Частые ошибки
- Не тот знак в характеристическом уравнении. Уравнение λ2−pλ−q=0: коэффициент q идёт со знаком «минус». Для xn=5xn−1−6xn−2 оно λ2−5λ+6=0, а не λ2−5λ−6=0.
- Дискриминант p2−4q. Для этого уравнения D=p2+4q.
- Перепутать корни в формулах констант. В c1 стоит λ2a−b, в c2 — b−λ1a; проверьте на n=0 и n=1.
- Взять один корень. Для разных корней нужны оба, иначе нельзя выполнить два начальных условия.
Проверь себя
1. Решите xn=3xn−1−2xn−2, x0=1, x1=3.
Решение
λ2−3λ+2=0: λ1=1, λ2=2. c2=λ2−λ1b−λ1a=13−1=2, c1=a−c2=−1. xn=−1+2⋅2n=2n+1−1. Первые члены 1,3,7,15,…
2. Решите xn=6xn−1−8xn−2, x0=0, x1=2.
Решение
λ2−6λ+8=0: λ1=2, λ2=4. c2=4−22−0=1, c1=−1. xn=4n−2n. Первые члены 0,2,12,56,…
3. Составьте характеристическое уравнение для xn=7xn−1−10xn−2 и найдите его корни.
Решение
λ2−7λ+10=0, D=49−40=9, корни λ=27±3: 2 и 5. Общее решение c12n+c25n.
4. Покажите, что последовательность xn=2n удовлетворяет xn=5xn−1−6xn−2.
Решение
5⋅2n−1−6⋅2n−2=2n−2(10−6)=4⋅2n−2=2n. Это следует и из того, что 2 — корень уравнения λ2−5λ+6=0.
Итог
- xn=pxn−1+qxn−2, x0=a, x1=b. Ищем xn=λn: получаем λ2−pλ−q=0, дискриминант D=p2+4q.
- Решения можно складывать и умножать на числа (суперпозиция).
- При D>0: xn=c1λ1n+c2λ2n, c2=λ2−λ1b−λ1a, c1=λ2−λ1λ2a−b.