bulgakov

39. Второй порядок: два вещественных корня

Если член последовательности зависит от двух предыдущих: xn=p xn−1+q xn−2x_n=p\,x_{n-1}+q\,x_{n-2}, — ищем решения в виде геометрической прогрессии xn=λnx_n=\lambda^n. Подстановка даёт характеристическое уравнение λ2−pλ−q=0\lambda^2-p\lambda-q=0. Если у него два разных вещественных корня λ1≠λ2\lambda_1\ne\lambda_2, то подходит любая комбинация c1λ1n+c2λ2nc_1\lambda_1^n+c_2\lambda_2^n, а числа c1,c2c_1,c_2 подбираются по первым двум членам.

Что пригодится из прошлого: рекуррентные соотношения первого порядка — мысль «решить соотношение значит найти формулу для xnx_n»; квадратные уравнения и дискриминант — из школьной алгебры. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача

Найти общий член последовательности, заданной условиями

xn=p⋅xn−1+q⋅xn−2,x0=a, x1=b,n=2,3,…(4)x_n=p\cdot x_{n-1}+q\cdot x_{n-2},\qquad x_0=a,\ x_1=b,\qquad n=2,3,\dots\tag{4}

где p,q,a,bp,q,a,b — заданные числа. Такое соотношение называется линейным (неизвестные члены входят только в первой степени), однородным (нет лишней добавки), второго порядка (член зависит от двух предыдущих), с постоянными коэффициентами (p,qp,q не меняются).

Нужны два начальных значения, x0x_0 и x1x_1: без них первые члены неизвестны, а каждый следующий получается из двух предыдущих.

Пример. xn=5xn−1−6xn−2x_n=5x_{n-1}-6x_{n-2}, x0=0x_0=0, x1=1x_1=1: получаем x2=5⋅1−6⋅0=5x_2=5\cdot1-6\cdot0=5, x3=5⋅5−6⋅1=19x_3=5\cdot5-6\cdot1=19, x4=5⋅19−6⋅5=65x_4=5\cdot19-6\cdot5=65, … Есть ли для этого общая формула?

Догадка: искать геометрическую прогрессию

Самая простая последовательность, у которой каждый член получается умножением на одно и то же число, — геометрическая прогрессия xn=λnx_n=\lambda^n (λ≠0\lambda\ne0). Проверим, при каком λ\lambda она подходит. Подставим в xn=p xn−1+q xn−2x_n=p\,x_{n-1}+q\,x_{n-2}:

λn=p λn−1+q λn−2.\lambda^n=p\,\lambda^{n-1}+q\,\lambda^{n-2}.

Разделим на λn−2≠0\lambda^{n-2}\ne0:

λ2−pλ−q=0.\boxed{\lambda^2-p\lambda-q=0}.

Это характеристическое уравнение соотношения (4). Его дискриминант D=p2+4qD=p^2+4q (так как в уравнении λ2−pλ−q=0\lambda^2-p\lambda-q=0 свободный член равен −q-q). Возможны три случая:

  • D>0D>0: два разных вещественных корня — разберём в этой главе;
  • D=0D=0: один корень (кратный);
  • D<0D<0: два комплексных корня.

Два последних случая — в следующей главе.

Принцип суперпозиции

Пусть последовательности unu_n и vnv_n удовлетворяют соотношению (4), то есть un=p un−1+q un−2u_n=p\,u_{n-1}+q\,u_{n-2} и vn=p vn−1+q vn−2v_n=p\,v_{n-1}+q\,v_{n-2}. Тогда для любых чисел c1,c2c_1,c_2 последовательность c1un+c2vnc_1u_n+c_2v_n тоже удовлетворяет (4):

c1un+c2vn=p (c1un−1+c2vn−1)+q (c1un−2+c2vn−2).c_1u_n+c_2v_n=p\,(c_1u_{n-1}+c_2v_{n-1})+q\,(c_1u_{n-2}+c_2v_{n-2}).

Умножьте первое равенство на c1c_1, второе на c2c_2 и сложите — получится именно это. То есть решения можно складывать и умножать на числа.

Случай D>0D>0: два вещественных корня

Пусть характеристическое уравнение имеет два разных вещественных корня λ1≠λ2\lambda_1\ne\lambda_2 (D=p2+4q>0D=p^2+4q>0). Тогда для любых вещественных c1,c2c_1,c_2 последовательности c1λ1nc_1\lambda_1^n и c2λ2nc_2\lambda_2^n удовлетворяют (4), а значит, и их сумма

xn=c1λ1n+c2λ2n.x_n=c_1\lambda_1^n+c_2\lambda_2^n.

Подбор констант. Подставим n=0n=0 и n=1n=1 в эту формулу и потребуем x0=ax_0=a, x1=bx_1=b:

{a=x0=c1+c2,b=x1=c1λ1+c2λ2.\begin{cases} a=x_0=c_1+c_2,\\ b=x_1=c_1\lambda_1+c_2\lambda_2. \end{cases}

Умножим первое уравнение на λ1\lambda_1 и вычтем из второго: b−λ1a=c2(λ2−λ1)b-\lambda_1a=c_2(\lambda_2-\lambda_1). Значит,

c2=b−λ1aλ2−λ1,c1=a−c2=λ2a−bλ2−λ1.c_2=\frac{b-\lambda_1a}{\lambda_2-\lambda_1},\qquad c_1=a-c_2=\frac{\lambda_2a-b}{\lambda_2-\lambda_1}.

(Деление возможно, потому что λ2≠λ1\lambda_2\ne\lambda_1.) Итого

xn=λ2a−bλ2−λ1 λ1n+b−λ1aλ2−λ1 λ2n(5)\boxed{x_n=\frac{\lambda_2a-b}{\lambda_2-\lambda_1}\,\lambda_1^n+\frac{b-\lambda_1a}{\lambda_2-\lambda_1}\,\lambda_2^n}\tag{5}

— решение соотношения (4) в случае D=p2+4q>0D=p^2+4q>0. Если поменять корни местами (λ1↔λ2\lambda_1\leftrightarrow\lambda_2), получится та же последовательность.

Замечание. Если q=0q=0, один из корней равен нулю (λ2−pλ=λ(λ−p)\lambda^2-p\lambda=\lambda(\lambda-p)). Формула (5) остаётся верной, если считать 00=10^0=1 (это нужно при n=0n=0).

Почему это единственное решение. Последовательность однозначно определена парой x0,x1x_0,x_1: по ним находится x2x_2, затем x3x_3 и так далее. Формула (5) удовлетворяет и соотношению, и обоим начальным условиям, значит, совпадает с искомой последовательностью.

Примеры

1. xn=5xn−1−6xn−2x_n=5x_{n-1}-6x_{n-2}, x0=0x_0=0, x1=1x_1=1. Характеристическое уравнение λ2−5λ+6=0\lambda^2-5\lambda+6=0, корни λ1=2\lambda_1=2, λ2=3\lambda_2=3 (D=25−24=1>0D=25-24=1>0). По формуле (5):

c1=3⋅0−13−2=−1,c2=1−2⋅03−2=1,xn=3n−2n.c_1=\frac{3\cdot0-1}{3-2}=-1,\qquad c_2=\frac{1-2\cdot0}{3-2}=1,\qquad x_n=3^n-2^n.
nn 0 1 2 3 4 5 6 7
xnx_n по правилу 0 1 5 19 65 211 665 2059
3n−2n3^n-2^n 0 1 5 19 65 211 665 2059

2. xn=xn−1+2xn−2x_n=x_{n-1}+2x_{n-2}, x0=1x_0=1, x1=1x_1=1. Уравнение λ2−λ−2=0\lambda^2-\lambda-2=0, D=1+8=9D=1+8=9, корни λ1=−1\lambda_1=-1, λ2=2\lambda_2=2. Константы:

c1=2⋅1−12−(−1)=13,c2=1−(−1)⋅13=23,c_1=\frac{2\cdot1-1}{2-(-1)}=\frac13,\qquad c_2=\frac{1-(-1)\cdot1}{3}=\frac23,

поэтому

xn=13(−1)n+23 2n=2n+1+(−1)n3.x_n=\frac13(-1)^n+\frac23\,2^n=\frac{2^{n+1}+(-1)^n}{3}.
nn 0 1 2 3 4 5 6 7 8
xnx_n по правилу 1 1 3 5 11 21 43 85 171
2n+1+(−1)n3\dfrac{2^{n+1}+(-1)^n}{3} 1 1 3 5 11 21 43 85 171

Частые ошибки

  • Не тот знак в характеристическом уравнении. Уравнение λ2−pλ−q=0\lambda^2-p\lambda-q=0: коэффициент qq идёт со знаком «минус». Для xn=5xn−1−6xn−2x_n=5x_{n-1}-6x_{n-2} оно λ2−5λ+6=0\lambda^2-5\lambda+6=0, а не λ2−5λ−6=0\lambda^2-5\lambda-6=0.
  • Дискриминант p2−4qp^2-4q. Для этого уравнения D=p2+4qD=p^2+4q.
  • Перепутать корни в формулах констант. В c1c_1 стоит λ2a−b\lambda_2a-b, в c2c_2 — b−λ1ab-\lambda_1a; проверьте на n=0n=0 и n=1n=1.
  • Взять один корень. Для разных корней нужны оба, иначе нельзя выполнить два начальных условия.

Проверь себя

1. Решите xn=3xn−1−2xn−2x_n=3x_{n-1}-2x_{n-2}, x0=1x_0=1, x1=3x_1=3.

Решение

λ2−3λ+2=0\lambda^2-3\lambda+2=0: λ1=1\lambda_1=1, λ2=2\lambda_2=2. c2=b−λ1aλ2−λ1=3−11=2c_2=\dfrac{b-\lambda_1a}{\lambda_2-\lambda_1}=\dfrac{3-1}{1}=2, c1=a−c2=−1c_1=a-c_2=-1. xn=−1+2⋅2n=2n+1−1x_n=-1+2\cdot2^n=2^{n+1}-1. Первые члены 1,3,7,15,…1,3,7,15,\dots

2. Решите xn=6xn−1−8xn−2x_n=6x_{n-1}-8x_{n-2}, x0=0x_0=0, x1=2x_1=2.

Решение

λ2−6λ+8=0\lambda^2-6\lambda+8=0: λ1=2\lambda_1=2, λ2=4\lambda_2=4. c2=2−04−2=1c_2=\dfrac{2-0}{4-2}=1, c1=−1c_1=-1. xn=4n−2nx_n=4^n-2^n. Первые члены 0,2,12,56,…0,2,12,56,\dots

3. Составьте характеристическое уравнение для xn=7xn−1−10xn−2x_n=7x_{n-1}-10x_{n-2} и найдите его корни.

Решение

λ2−7λ+10=0\lambda^2-7\lambda+10=0, D=49−40=9D=49-40=9, корни λ=7±32\lambda=\dfrac{7\pm3}2: 22 и 55. Общее решение c1 2n+c2 5nc_1\,2^n+c_2\,5^n.

4. Покажите, что последовательность xn=2nx_n=2^n удовлетворяет xn=5xn−1−6xn−2x_n=5x_{n-1}-6x_{n-2}.

Решение

5⋅2n−1−6⋅2n−2=2n−2(10−6)=4⋅2n−2=2n5\cdot2^{n-1}-6\cdot2^{n-2}=2^{n-2}(10-6)=4\cdot2^{n-2}=2^n. Это следует и из того, что 22 — корень уравнения λ2−5λ+6=0\lambda^2-5\lambda+6=0.

Итог

  • xn=p xn−1+q xn−2x_n=p\,x_{n-1}+q\,x_{n-2}, x0=ax_0=a, x1=bx_1=b. Ищем xn=λnx_n=\lambda^n: получаем λ2−pλ−q=0\lambda^2-p\lambda-q=0, дискриминант D=p2+4qD=p^2+4q.
  • Решения можно складывать и умножать на числа (суперпозиция).
  • При D>0D>0: xn=c1λ1n+c2λ2nx_n=c_1\lambda_1^n+c_2\lambda_2^n, c2=b−λ1aλ2−λ1c_2=\dfrac{b-\lambda_1a}{\lambda_2-\lambda_1}, c1=λ2a−bλ2−λ1c_1=\dfrac{\lambda_2a-b}{\lambda_2-\lambda_1}.
ПрактикаЗагружаем тест…