Материал: Prak_alg
56
3.2
Линейные
рекуррентные
соотношения
с
постоянными
коэффициентами
Для
решения
рекуррентных
соотношений
общих
правил
не
существу
-
ет
.
Однако
существует
весьма
часто
встречающийся
класс
соотношений
,
решаемых
единообразным
методом
.
Это
–
рекуррентные
соотношения
вида
)
n
(
f
a
...
)
k
n
(
f
a
)
k
n
(
f
a
)
k
n
(
f
k
+
+
-
+
+
-
+
=
+
2
1
2
1
,
где
k
a
,...,
a
,
a
2
1
–
некоторые
числа
.
Такие
соотношения
называются
ли
-
нейными
рекуррентными
соотношениями
с
постоянными
коэффици
-
ентами
.
Рассмотрим
,
как
решаются
такие
соотношения
при
2
=
k
,
то
есть
изучим
соотношения
вида
1
2
(
2)
(
1)
( ).
f n
a f n
a f n
+
=
+ +
(3)
Решение
этих
соотношений
основано
на
следующих
двух
утвержде
-
ниях
:
1)
Если
)
n
(
f
1
и
)
n
(
f
2
являются
решениями
рекуррентного
соотноше
-
ния
(3),
то
при
любых
A
и
B
последовательность
)
n
(
Bf
)
n
(
Af
)
n
(
f
2
1
+
=
также
является
решением
этого
соотношения
.
В
самом
деле
,
по
условию
имеем
)
n
(
f
a
)
n
(
f
a
)
n
(
f
1
2
1
1
1
1
2
+
+
=
+
и
2
1 2
2 2
(
2)
(
1)
( ).
f n
a f n
a f n
Умножим
эти
равенства
на
A
и
B
соответственно
и
сложим
полу
-
ченные
тождества
.
Мы
получим
,
что
1
2
1
1
2
2
1
(
2)
(
2)
[
(
1)
(
1)]
[
( )
( )].
Af n
Bf n
a Af n
Bf n
a Af n
Bf n
+ +
+
=
+ +
+
+
+
+
Это
означает
,
что
)
n
(
Bf
)
n
(
Af
)
n
(
f
2
1
+
=
является
решением
нашего
соотношения
.
2)
Если
число
1
r
является
корнем
квадратного
уравнения
2
1
2
a
r
a
r
+
=
,
то
последовательность
,...
r
...,
,
r
,
r
,
n
1
1
2
1
1
1
-
является
решением
рекуррентного
соотношения
)
n
(
f
a
)
n
(
f
a
)
n
(
f
2
1
1
2
+
+
=
+
.
Наряду
с
последовательностью
{ }
1
1
-
n
r
любая
последовательность
вида
m
n
r
)
n
(
f
+
=
1
,
1, 2, ...
n
=
также
является
решением
исследуемого
соотношения
.
Из
утверждений
1)
и
2)
вытекает
следующее
правило
решения
ли
-
нейных
рекуррентных
соотношений
второго
порядка
с
постоянными
ко
-
эффициентами
:
57
Пусть
дано
рекуррентное
соотношение
1
2
(
2)
(
1)
( ).
f n
a f n
a f n
+
=
+ +
Составим
квадратное
уравнение
2
1
2
a
r
a
r
+
=
, (4)
которое
называется
характеристическим
для
данного
соотношения
.
Если
это
уравнение
имеет
два
различных
корня
1
r
и
2
r
,
то
общее
реше
-
ние
рекуррентного
соотношения
имеет
вид
2
2
2
1
1
1
-
-
+
=
n
n
r
C
r
C
)
n
(
f
.
Действительно
,
по
утверждению
2)
1
1
1
-
=
n
r
)
n
(
f
и
1
2
2
-
=
n
r
)
n
(
f
явля
-
ются
решениями
нашего
соотношения
.
По
утверждению
1)
и
2
2
2
1
1
1
-
-
+
=
n
n
r
C
r
C
)
n
(
f
является
его
решением
.
Надо
показать
,
что
любое
решение
соотношения
можно
записать
в
этом
виде
.
Но
любое
решение
ли
-
нейного
рекуррентного
соотношения
второго
порядка
определяется
значе
-
ниями
)
(
f
1
и
)
(
f
2
.
Поэтому
достаточно
показать
,
что
система
уравнений
î
í
ì
=
+
=
+
b
r
C
r
C
a
C
C
2
2
1
1
2
1
имеет
решение
при
любых
a
и
b
.
Этими
решениями
являются
.
r
r
b
ar
C
,
r
r
ar
b
C
2
1
1
2
2
1
2
1
-
-
=
-
-
=
Случай
,
когда
оба
корня
уравнения
2
1
2
a
r
a
r
+
=
совпадают
друг
с
другом
,
мы
разберем
несколько
позже
.
Рассмотрим
пример
.
При
изучении
чисел
Фибоначчи
мы
пришли
к
рекуррентному
соот
-
ношению
)
n
(
f
)
n
(
f
)
n
(
f
2
1
-
+
-
=
.
Для
него
характеристическое
уравнение
имеет
вид
1
2
+
=
r
r
.
Корнями
этого
квадратного
уравнения
являются
числа
.
r
,
r
2
5
1
2
5
1
1
1
-
=
+
=
Поэтому
общее
решение
соотношения
Фибоначчи
имеет
вид
n
n
C
C
)
n
(
f
÷÷
ø
ö
çç
è
æ -
+
÷÷
ø
ö
çç
è
æ +
=
2
5
1
2
5
1
2
1
.
58
3.3
Случай
равных
корней
характеристического
уравнения
Остановимся
теперь
на
случае
,
когда
оба
корня
характеристического
уравнения
совпадают
:
2
1
r
r
=
.
В
этом
случае
выражение
1
2
2
1
1
1
-
-
+
n
n
r
C
r
C
уже
не
будет
общим
решением
.
Ведь
из
-
за
того
,
что
2
1
r
r
=
,
это
решение
можно
записать
в
виде
( ) (
)
.
Cr
r
C
C
n
f
n
n
1
1
1
1
2
1
=
-
=
+
=
У
нас
остается
только
одно
произвольное
постоянное
C
,
и
выбрать
его
так
,
чтобы
удовлетворить
двум
начальным
условиям
( )
( )
b
f
,
a
f
=
=
2
1
,
вообще
говоря
,
невозможно
.
Поэтому
надо
найти
какое
-
нибудь
второе
решение
отличное
от
( )
1
1
1
-
=
n
r
n
f
.
Оказывается
,
таким
решением
является
( )
1
1
2
-
=
n
nr
n
f
.
В
самом
деле
,
если
квадратное
уравнение
2
1
2
a
r
a
r
+
=
имеет
два
совпадающих
корня
2
1
r
r
=
,
то
по
теореме
Виета
2
1
2
1
1
2
r
a
,
r
a
-
=
=
.
Поэтому
наше
урав
-
нение
записывается
так
:
2
1
1
2
2
r
r
r
r
-
=
.
Тогда
рекуррентное
соотношение
имеет
такой
вид
:
(
)
(
)
( )
n
f
r
n
f
r
n
f
2
1
1
1
2
2
-
+
=
+
. (5)
Проверим
,
что
( )
1
1
2
-
=
n
nr
n
f
действительно
является
его
решением
.
Имеем
(
) (
)
1
1
2
2
2
+
+
=
+
n
r
n
n
f
,
а
(
) (
)
n
r
n
n
f
1
2
1
1
+
=
+
.
Подставляя
эти
значе
-
ния
в
соотношение
(4),
получаем
очевидное
тождество
(
)
(
)
1
1
1
1
1
1
1
2
2
+
+
+
-
+
=
+
n
n
n
nr
r
n
r
n
.
Значит
,
1
1
-
n
nr
—
решение
нашего
соотношения
.
Теперь
уже
знаем
два
решения
( )
1
1
1
-
=
n
r
n
f
и
( )
1
1
2
-
=
n
nr
n
f
заданного
соотношения
.
Его
общее
решение
пишется
так
:
( )
(
)
n
C
C
r
nr
C
r
C
n
f
n
r
n
n
2
1
1
1
1
2
1
1
1
+
=
+
=
-
-
-
.
Путем
подбора
1
C
и
2
C
можно
удовлетворить
любым
начальным
ус
-
ловиям
.
Линейные
рекуррентные
соотношения
с
постоянными
коэффициен
-
тами
,
порядок
которых
больше
двух
,
решаются
таким
же
способом
.
Пусть
соотношение
имеет
вид
(
)
(
)
( )
n
f
a
k
n
f
a
k
n
f
k
+
+
-
+
=
+
K
1
1
.
Составляем
характеристическое
уравнение
k
k
k
a
r
a
r
+
+
=
-
K
1
1
.
Если
все
корни
k
r
,
,
r
K
1
этого
алгебраического
уравнения
k
-
й
степе
-
ни
различны
,
то
общее
решение
имеет
вид
( )
1
1
2
2
1
1
1
-
-
-
+
+
+
=
n
k
k
n
n
r
C
r
C
r
C
n
f
K
.
59
Если
же
,
например
,
s
r
r
r
=
=
=
K
2
1
,
то
этому
корню
соответствуют
решения
( )
( )
( )
( )
1
1
1
1
1
2
3
1
1
2
1
1
1
-
-
-
-
-
=
=
=
=
n
s
s
n
n
n
r
n
n
f
,
,
r
n
n
f
,
nr
n
f
,
r
n
f
K
рассматриваемого
рекуррентного
соотношения
.
В
общем
решении
этому
корню
соответствует
часть
[
]
1
2
3
2
1
1
1
-
-
+
+
+
+
s
s
n
n
C
n
C
n
C
C
r
K
.
Составляя
такие
выражения
для
всех
корней
и
складывая
их
,
получа
-
ем
общее
решение
.
Например
,
решим
рекуррентное
соотношение
(
)
(
)
(
)
(
)
( )
n
f
n
f
n
f
n
f
n
f
8
1
4
2
6
3
5
4
+
+
-
+
-
+
=
+
.
Характеристическое
уравнение
имеет
здесь
вид
0
8
4
6
5
2
3
4
=
-
+
+
-
r
r
r
r
.
Решая
его
,
получаем
корни
.
r
,
r
,
r
,
r
1
2
2
2
4
3
2
1
-
=
=
=
=
Значит
,
общее
решение
нашего
соотношения
имеет
следующий
вид
:
( )
[
]
( )
1
4
2
3
2
1
1
1
2
-
-
-
+
+
+
=
n
n
C
n
C
n
C
C
n
f
.
ЗАДАЧИ
И
УПРАЖНЕНИЯ
1.
Написать
первые
пять
членов
решения
рекуррентного
соотноше
-
ния
(
)
(
)
( )
n
f
n
f
n
f
3
1
2
2
-
+
=
+
,
удовлетворяющего
заданным
начальным
условиям
:
1)
( )
( )
1
0
;
2
1
f
f
=
ìï
í
=
ïî
2)
( )
( )
1
1
;
2
1
f
f
= -
ìï
í
=
ïî
3)
( )
( )
1
3
;
2
0
f
f
=
ìï
í
=
ïî
4)
( )
( )
1
2
;
2
1
f
f
=
ìï
í
=
ïî
5)
( )
( )
1 2
.
2
8
f
f
=
ìï
í
=
ïî
2.
Проверить
,
являются
ли
данные
функции
решениями
данных
ре
-
куррентных
соотношений
:
1)
(
)
(
)
( )
( )
( )
( )
.
n
,
n
n
,
n
;
n
f
n
f
n
f
n
3
1
2
2
5
1
2
2
3
2
1
=
+
=
×
=
-
+
=
+
j
j
j
2)
(
)
(
)
( )
( )
( )
( )
7
1
3
5
2
3
1
4
2
3
2
1
=
-
×
=
=
-
+
=
+
n
,
n
,
n
n
;
n
f
n
f
n
f
n
j
j
j
3.
Найти
общее
решение
рекуррентных
соотношений
:
1)
(
2) 7 (
1) 12 ( ) 0;
f n
f n
f n
+ -
+ +
=
2)
0
10
1
3
2
=
-
+
+
+
)
n
(
f
)
n
(
f
)
n
(
f
;
3)
0
13
1
4
2
=
+
+
-
+
)
n
(
f
)
n
(
f
)
n
(
f
;
60
4)
0
9
2
=
+
+
)
n
(
f
)
n
(
f
;
5)
(
2) 4 (
1) 4 ( ) 0;
f n
f n
f n
+ +
+ +
=
6)
(
)
(
)
(
)
( )
3
9
2
26
1
24
0;
f n
f n
f n
f n
+ -
+
+
+ -
=
7)
(
)
(
)
(
)
( )
3
3
2
3
1
0;
f n
f n
f n
f n
+ +
+
+
+ +
=
8)
(
)
( )
.
n
f
n
f
0
4
4
=
+
+
4.
Найти
( )
n
f
,
зная
рекуррентное
соотношение
и
начальные
члены
:
1)
2
5
1
6
0,
1
1,
2
7;
f n
f n
f n
f
f
2)
2
4
1
4
0,
1
2,
2
4;
f n
f n
f n
f
f
3)
1
1
2
1
0,
1
,
2
;
4
2
f n
f n
f n
f
f
4)
(
)
(
)
( )
( )
( )
;
f
;
f
;
n
f
n
f
n
f
4
2
2
1
1
2
2
=
=
-
+
=
+
5)
(
)
(
)
( )
( )
( )
;
f
;
f
;
n
f
n
f
n
f
5
2
1
1
5
1
4
2
=
=
+
+
=
+
6)
(
)
(
)
( )
( )
( )
;
f
;
f
;
n
f
n
f
n
f
3
2
0
1
9
1
6
2
=
=
-
+
=
+
7)
(
)
( )
(
)
( )
( )
;
f
;
f
;
n
f
n
f
n
f
2
2
1
1
1
2
2
=
=
+
-
=
+
8)
2
8
1 ;
1
4.
f n
f n
f
5.
Привести
пример
линейного
рекуррентного
соотношения
2-
го
по
-
рядка
,
среди
решений
которого
имеются
следующие
функции
:
1)
( )
;
n
n
3
=
j
2)
( )
3 2
5 ;
n
n
n
j
= ×
-
3)
( )
;
n
n
1
2
-
=
j
4)
( )
17.
n
n
j
= -
6.
Найти
такую
последовательность
,
что
a
a
2
2
1
cos
)
(
f
,
cos
)
(
f
=
=
и
0
1
2
2
=
+
+
-
+
)
n
(
f
)
n
(
f
cos
)
n
(
f
a
.
7.
Найти
последовательность
такую
,
что
n
)
n
(
f
)
n
(
f
)
n
(
f
2
8
1
2
2
=
-
+
+
+
.
8.
Проанализировать
рекуррентное
соотношение
(3),
если
известно
,
что
один
из
корней
характеристического
уравнений
(4)
равен
нулю
.
Каков
порядок
этого
рекуррентного
соотношения
?
Доказать
,
что
его
общее
ре
-
шение
в
данном
случае
имеет
вид
:
(
)
n
a
C
C
,
n
1
1
=
j
.
Что
можно
сказать
о
ре
-
шении
рекуррентного
соотношения
(3),
если
оба
корня
характеристическо
-
го
уравнения
(4)
равны
нулю
?