Возвратные последовательности | Математика, которая мне нравится

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

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

$x_n=px_{n-1}+qx_{n-2}\quad(k>2) \eqno(1)$

и заданы $x_1,x_2$ .

Замечание. Будем считать, что $p\ne0,q\ne0$ , иначе имеем геометрическую прогрессию.

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

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

$x^2-px-q=0 \eqno(2)$

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

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

$x_n=c_1\alpha^n+c_2\beta^n,$

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

$\left\{\begin{array}{l} x_1=c_1\alpha+c_2\beta\\ x_2=c_1\alpha^2+c_2\beta^2 \end{array}\right.\eqno(3)$

Доказательство. По формулам Виета $p=\alpha+\beta,q=-\alpha\beta$ . Доказательство будем проводить методом математической индукции. Однако в нашем случае базу индукции придется проверять не только для $n=1$ , но и для $n=2$ .

$\left\{\begin{array}{l} x_1=c_1\alpha^1+c_2\beta^1\\ x_2=c_1\alpha^2+c_2\beta^2 \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} 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] =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 =c_1\alpha^{k+1}+c_2\beta^{k+1}. \end{array}$

Пример. $p=3,q=-2\Longrightarrow\alpha=1,\beta=2,x_1=3,x_2=7$ .

$\left\{\begin{array}{l} 3=c_1+2c_2\\ 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}.$

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

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

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

$x_n=(c_1+nc_2)\alpha^n,$

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

$(c_1+c_2)\alpha=x_1,\ (c_1+2c_2)\alpha^2=x_2.$

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

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

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

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

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

Пусть $j=k+1$ . Тогда

$\begin{array}{l} x_{k+1}=2\alpha x_k-\alpha^2x_{k-1}=2\alpha(c_1+kc_2)\alpha^k- \alpha^2(c_1+(k-1)c_2)\alpha^{k-1}=\\[2mm] =2c_1\alpha^{k+1}+2kc_2\alpha^{k+1}-c_1\alpha^{k+1}-(k-1)c_2\alpha^{k+1}=\\[2mm] =c_1\alpha^{k+1}+(k+1)c_2\alpha^{k+1}=(c_1+(k+1)c_2)\alpha^{k+1}. \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</tex>.$
3. Пусть

$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,$

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

$S=a_1+a_2+\dots+a_n,\ S_1={1\over a_1}+{1\over a_2}+\dots+{1\over a_n},$

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

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

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

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

$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).$

Комментарии (RSS) | Трекбек

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

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

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

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

[Ответить]
31 Май 2012, 15:16
2 Елизавета Александровна Калинина:

По-моему, там тоже все притянуто за уши. Откуда
$x_n=\lambda^n$

? Если хотите честный вывод, читайте тут: http://hijos.ru/olimpiadnikam/4-rekurrentnye-sootnosheniya-i-proizvodyashhie-funkcii/

[Ответить]
31 Май 2012, 18:02
3 Меня терзают смутные сомнения...:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Май 7th, 2015 at 13:44
Спасибо, так и есть. Исправила.

[Ответить]
7 Май 2015, 8:28
4 Меня опять терзают смутные сомнения:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Май 8th, 2015 at 14:07
Спасибо, Вы правы. Исправила.

[Ответить]
8 Май 2015, 6:33
5 Меня продолжают терзать смутные сомнения:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Май 11th, 2015 at 13:53
Спасибо, исправила. Так да, действительно база индукции очевидна. Мы же $c_1$ и $c_2$ находим из тех условий, что база индукции выполняется.

[Ответить]
9 Май 2015, 22:33
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:
Май 14th, 2015 at 7:35
Дело в маленькой опечатке в самом первом $(1)$ выражении. Там должно быть $n>2$ . Значит и базу индукции надо доказывать для $n>2$ , то есть для $(n=3)$ и $(n=4)$ . Я проверил для первой теоремы – все в порядке а вот для своего софизма при $(n=3)$ получил $x_2\alpha=x_2\beta$ – то есть база не доказана и софизм опровергнут.

[Ответить]
13 Май 2015, 8:03
7 Меня терзают смутные сомнения...:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Май 27th, 2015 at 0:32
Я не очень понимаю, зачем тут тригонометрические функции? Да, нужно формулу подобрать, а потом доказать ее по индукции.

[Ответить]
Меня терзают смутные сомнения... Reply:
Май 27th, 2015 at 6:24
В том-то и дело, что не могу ничего толком подобрать лучше чем

$a_n=(1-cos(2\pi*n/3))*2/3$

– у последовательности период равен 3-м. За доказательство даже не берусь

[Ответить]
Елизавета Александровна Калинина Reply:
Май 28th, 2015 at 18:43
Ну, если Вам не нравится тригонометрия, то можно взять дробную часть числа – это тоже периодическая функция.

[Ответить]
Меня больше не терзают сомнения. Reply:
Май 30th, 2015 at 0:32
Елизавета Александровна, большое спасибо за интересный сайт!
Задача 10 сильно оличается от всех остальных на этой странице. Хотя ее решение (с подсказкой) и выглядит простым, предлагаю отметить задачу звездочкой *

[Ответить]
Елизавета Александровна Калинина Reply:
Июнь 1st, 2015 at 19:27
Спасибо! Звездочку поставила.

[Ответить]
26 Май 2015, 4:51

Математика, которая мне нравится

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

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

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

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

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

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

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

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

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

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер