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

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

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

и заданы x_1,x_2.

Замечание. Будем считать, что pne0,qne0, иначе имеем геометрическую прогрессию.

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

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

    [x^2-px-q=0 eqno(2)]

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

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

    [x_n=c_1alpha^n+c_2beta^n,]

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

    [left{begin{array}{l} x_1=c_1alpha+c_2beta\ x_2=c_1alpha^2+c_2beta^2 end{array}right.eqno(3)]

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

    [left{begin{array}{l} x_1=c_1alpha^1+c_2beta^1\ x_2=c_1alpha^2+c_2beta^2 end{array}right.]

А это верно, поскольку c_1 и c_2 мы находили из системы (3).

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

    [x_j=c_1alpha^j+c_2beta^j.]

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

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

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

    [x_k=c_1alpha^k+c_2beta^k,x_{k-1}=c_1alpha^{k-1}+c_2beta^{k-1},]

получаем

    [begin{array}{l} x_{k+1}=(alpha+beta)(c_1alpha^k+c_2beta^k)-alphabeta(c_1alpha^{k-1}+c_2beta^{k-1})=\[2mm] =c_1alpha^{k+1}+c_2alphabeta^k+c_1alpha^kbeta+c_2beta^{k+1}- c_1alpha^kbeta-c_2alphabeta^k =c_1alpha^{k+1}+c_2beta^{k+1}. end{array}]

Пример. p=3,q=-2Longrightarrowalpha=1,beta=2,x_1=3,x_2=7.

    [left{begin{array}{l} 3=c_1+2c_2\ 7=c_1+4c_2end{array}right.Longrightarrow c_1=-1,c_2=2,x_k=-1cdot1^k+2cdot2^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=2alpha,q=-alpha^2.]

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

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

    [x_j=(c_1+jc_2)alpha^j.]

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

    [begin{array}{l} x_{k+1}=2alpha x_k-alpha^2x_{k-1}=2alpha(c_1+kc_2)alpha^k- alpha^2(c_1+(k-1)c_2)alpha^{k-1}=\[2mm] =2c_1alpha^{k+1}+2kc_2alpha^{k+1}-c_1alpha^{k+1}-(k-1)c_2alpha^{k+1}=\[2mm] =c_1alpha^{k+1}+(k+1)c_2alpha^{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+5cdot2^n,]

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

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

и начальным условиям a_1=13,a_2=29</tex>.
3. Пусть

    [a_{n+1}={a_n+b_nover 2},b_{n+1}={a_{n+1}+b_nover 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_1cdot a_2timesdotstimes a_n,]

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

    [S=a_1+a_2+dots+a_n, S_1={1over a_1}+{1over a_2}+dots+{1over 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=1quad (nge3).]

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

    [a_n={a_{n-1}a_{n-2}over 3a_{n-2}-2a_{n-1}},quad a_1=1/2,a_2=1/3quad(nge3).]

Ссылка на основную публикацию