5. Возвратные последовательности

Рассмотрим возвратную последовательность

<br />
x_n=px_{n-1}+qx_{n-2}\quad(k>2) \mbox{\hskip8cm}(1)<br />

и заданы x_1,x_2<tex>.</p>
<p><strong> Замечание.</strong> Будем считать, что <tex>p\ne0,q\ne0, иначе имеем геометрическую прогрессию.

Итак, найдем выражение для x_n через x_1,x_2 и номер n.

Определение. Уравнение

<br />
x^2-px-q=0\mbox{\hskip10,5cm} (2)

называется характеристическим уравнением последовательности (1).

Теорема. Пусть уравнение (2) имеет два различных корня \alpha и \beta. Тогда

<br />
x_n=c_1\alpha^n+c_2\beta^n,<br />

и значения c_1 и c_2 определяются из системы уравнений
 \left\{\begin{array}{l}<br />
x_1=c_1\alpha+c_2\beta\\<br />
x_2=c_1\alpha^2+c_2\beta^2<br />
\end{array}\right.\mbox{\hskip9,5cm}(3)<br />

Доказательство. По формулам Виета p=\alpha+\beta,q=-\alpha\beta. Доказательство будем проводить методом математической индукции. Однако в нашем случае базу индукции придется проверять не только для n=1, но и для n=2.
\left\{\begin{array}{l}<br />
x_1=c_1\alpha^1+c_2\beta^1\\<br />
x_2=c_1\alpha^2+c_2\beta^2<br />
\end{array}\right.
А это верно, поскольку c_1 и c_2 мы находили из системы (3).

Предположим теперь, что для всех членов последовательности с номерами не больше k выполнено

x_j=c_1\alpha^j+c_2\beta^j.

Рассмотрим x_{k+1}. Он выражается через предыдущие два члена x_k,x_{k-1} с помощью рекуррентного соотношения:

x_{k+1}=px_k+qx_{k-1}=(\alpha+\beta)x_k-\alpha\beta x_{k-1}.

Отсюда, поскольку

x_k=c_1\alpha^k+c_2\beta^k,x_{k-1}=c_1\alpha^{k-1}+c_2\beta^{k-1},

получаем
\begin{array}{l}<br />
x_{k+1}=(\alpha+\beta)(c_1\alpha^k+c_2\beta^k)-\alpha\beta(c_1\alpha^{k-1}+c_2\beta^{k-1})=\\[2mm]<br />
=c_1\alpha^{k+1}+c_2\alpha\beta^k+c_1\alpha^k\beta+c_2\beta^{k+1}- c_1\alpha^k\beta-c_2\alpha\beta^k<br />
=c_1\alpha^{k+1}+c_2\beta^{k+1}.<br />
\end{array}

Пример. p=3,q=-2\Longrightarrow\alpha=1,\beta=2,x_1=3,x_2=7.
\left\{\begin{array}{l}<br />
3=c_1+2c_2\\<br />
7=c_1+4c_2\end{array}\right.\Longrightarrow c_1=-1,c_2=2,x_k=-1\cdot1^k+2\cdot2^k=-1+2^{k+1}.<br />

Задача. Решить возвратную последовательность

x_n=7x_{n-1}-10x_{n-2},x_1=7,x_2=39.

Теорема. Пусть уравнение (2) имеет один корень \alpha=\beta. Тогда

<br />
x_n=(c_1+nc_2)\alpha^n,<br />

и значения c_1 и c_2 определяются из системы уравнений

<br />
(c_1+c_2)\alpha=x_1,\ (c_1+2c_2)\alpha^2=x_2.<br />

Доказательство.

p=2\alpha,q=-\alpha^2.

База индукции верна.

Предположим, что для всех j\le k

x_j=(c_1+jc_2)\alpha^j.

Пусть j=k+1. Тогда
\begin{array}{l}<br />
x_{k+1}=2\alpha x_k-\alpha^2x_{k-1}=2\alpha(c_1+kc_2)\alpha^k-<br />
\alpha^2(c_1+(k-1)c_2)\alpha^{k-1}=\\[2mm]<br />
=2c_1\alpha^{k+1}+2kc_2\alpha^{k+1}-c_1\alpha^{k+1}-(k-1)c_2\alpha^{k+1}=\\[2mm]<br />
=c_1\alpha^{k+1}+(k+1)c_2\alpha^{k+1}=(c_1+(k+1)c_2)\alpha^{k+1}.<br />
\end{array}

Задача. Решить возвратную последовательность

x_n=2x_{n-1}-x_{n-2},x_1=2,x_2=3.

Определение. Последовательность (a_n) называется периодической, если существует натуральное k, такое, что a_{n+k}=a_n для всех натуральных n.

Задачи.
1. Найти 1987-й член последовательности

x_n=x_{n-1}-x_{n-2},x_1=2,x_2=5.

2. Доказать, что последовательность (a_n), где

a_n=3^n+5\cdot2^n,

удовлетворяет рекуррентному соотношению

a_n=5a_{n-1}-6a_{n-2}

и начальным условиям a_1=13,a_2=29.

3. Пусть

\displaystyle a_{n+1}={a_n+b_n\over 2},b_{n+1}={a_{n+1}+b_n\over 2}.

Выразить a_n и b_n через a_1,b_1 и n.

4. Дана последовательность (a_n):

a_{n+1}=a_n^2,a_1=a.

Выяснить, при каких значениях a последовательность (a_n) является периодической.

5. Дана последовательность (a_n):

a_{n+2}=2a_{n+1}+3a_n,\quad a_1=a,a_2=b.

Выяснить, существуют ли такие положительные a и b, что последовательность a_n является периодической.

6. Решить рекуррентные соотношения:

а) r_{n+2}=5r_{n+1}-4r_n,r_1=1,r_2=-1;

б) r_{n+2}=-8r_{n+1}-16r_n,r_1=2,r_2=3.

7. Найти общее выражение n-го члена последовательности Фибоначчи.

8. Пусть у последовательности разности двух соседних членов образуют арифметическую прогрессию с разностью d. Найти n-й ее член и сумму первых n членов, если первый член равен a, а разность между вторым и первым — d.

9. Найти произведение

P=a_1\cdot a_2\times\dots\times a_n,

если известно, что

\displaystyle S=a_1+a_2+\dots+a_n,\<br />
S_1={1\over a_1}+{1\over a_2}+\dots+{1\over a_n},

и числа a_1,a_2,\dots,a_n образуют геометрическую прогрессию.

10*. Решить рекуррентное соотношение

\displaystyle a_n={a_{n-1}-a_{n-2}\over 2a_{n-1}-1},\quad a_1=a_2=1\quad (n\ge3).

11. Решить рекуррентное соотношение

\displaystyle a_n={a_{n-1}a_{n-2}\over 3a_{n-2}-2a_{n-1}},\quad a_1=1/2,a_2=1/3\quad(n\ge3).

Комментариев: 16

  1. 1 Вася Пупкин:

    Было бы неплохо дать вывод характеристического уравнения, а то впадаешь в ступор и перестаешь воспринимать дальнейший материал…

    Вот здесь хорошо описано http://www.resolventa.ru/spr/algebra/rec1.htm

    [Ответить]

  2. 2 Елизавета Александровна Калинина:

    По-моему, там тоже все притянуто за уши. Откуда x_n=\lambda^n? Если хотите честный вывод, читайте тут: http://hijos.ru/olimpiadnikam/4-rekurrentnye-sootnosheniya-i-proizvodyashhie-funkcii/

    [Ответить]

  3. 3 Меня терзают смутные сомнения...:

    По поводу условия задачи 2. Не должно-ли второе выражение (рекуррентное соотношение) быть a_n=5a_{n-1}-6a_{n-2} ?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо, так и есть. Исправила.

    [Ответить]

  4. 4 Меня опять терзают смутные сомнения:

    по поводу задачи 4. Не могу найти в условии переменную a значения которой надо выяснить :(

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо, Вы правы. Исправила.

    [Ответить]

  5. 5 Меня продолжают терзать смутные сомнения:

    Вторая теорема – там где с одним корнем. В выражении следующем за “и значения c_1 и c_2 определяются из системы уравнений” не пропущена-ли \alpha, а то задачи решаются только для \alpha=1. А в доказательстве той-же второй теоремы получается что база индукции принята за очевидное – там только формулы Виета для случая с одним корнем.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо, исправила. Так да, действительно база индукции очевидна. Мы же c_1 и c_2 находим из тех условий, что база индукции выполняется.

    [Ответить]

  6. 6 Меня снова терзают смутные сомнения:

    Предположим, а это только предположение, догадка, что
    x_n=c_1\alpha^{n-1}+c_2\beta^{n-1},
    и значения c_1 и c_2 определяются из системы уравнений
    x_1=c_1+c_2, x_2=c_1\alpha+c_2\beta
    Попытаемся доказать это утверждение, воспользовавшись приемами доказательства первой теоремы. Базу принимаем как очевидное из системы уравнений. Далее, исходя из
    x_k=c_1\alpha^{k-1}+c_2\beta^{k-1},
    x_{k-1}=c_1\alpha^{k-2}+c_2\beta^{k-2}
    и формул Виета, имеем
    x_{k+1}=(\alpha+\beta)(c_1\alpha^{k-1}+c_2\beta^{k-1})-\alpha\beta(c_1\alpha^{k-2}+c_2\beta^{k-2})=
    =c_1\alpha^k+c_2\alpha\beta^{k-1}+c_1\alpha^{k-1}\beta+c_2\beta^k-c_1\alpha^{k-1}\beta-c_2\alpha\beta^{k-1}=
    =c_1\alpha^k+c_2\beta^k ч.т.д. :(
    Понимаю, что все это сильно смахивает на софистику, но, тем не мение, следуя методике доказательства теорем на этой странице, удалось доказать ложное утверждение. Как же это получилось?

    [Ответить]

    Меня больше не терзают сомнения. Reply:

    Дело в маленькой опечатке в самом первом (1) выражении. Там должно быть n>2. Значит и базу индукции надо доказывать для n>2, то есть для (n=3) и (n=4). Я проверил для первой теоремы – все в порядке :) а вот для своего софизма при (n=3) получил x_2\alpha=x_2\beta – то есть база не доказана и софизм опровергнут.

    [Ответить]

  7. 7 Меня терзают смутные сомнения...:

    Помогите пожалуйста с задачей 10. У меня получается последовательность 1,1,0,1,1,0… с периодом 3. Можно-ли решить эту задачу без применения тригонометрических функций?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Я не очень понимаю, зачем тут тригонометрические функции? Да, нужно формулу подобрать, а потом доказать ее по индукции.

    [Ответить]

    Меня терзают смутные сомнения... Reply:

    В том-то и дело, что не могу ничего толком подобрать лучше чем
    a_n=(1-cos(2\pi*n/3))*2/3 – у последовательности период равен 3-м. За доказательство даже не берусь :(

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Ну, если Вам не нравится тригонометрия, то можно взять дробную часть числа – это тоже периодическая функция.

    [Ответить]

    Меня больше не терзают сомнения. Reply:

    Елизавета Александровна, большое спасибо за интересный сайт!
    Задача 10 сильно оличается от всех остальных на этой странице. Хотя ее решение (с подсказкой) и выглядит простым, предлагаю отметить задачу звездочкой * :)

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо! :-) Звездочку поставила.

    [Ответить]

Оставьте свой отзыв

Добавить изображение