Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 56 стр.

UptoLike

Составители: 

56
3.2 Линейные рекуррентные соотношения
с постоянными коэффициентами
Для решения рекуррентных соотношений общих правил не существу-
ет. Однако существует весьма часто встречающийся класс соотношений,
решаемых единообразным методом. Это рекуррентные соотношения вида
)n(fa...)kn(fa)kn(fa)kn(f
k
+
+
-
+
+
-
+
=
+
21
21
,
где
k
a,...,a,a
21
некоторые числа. Такие соотношения называются ли-
нейными рекуррентными соотношениями с постоянными коэффици-
ентами.
Рассмотрим, как решаются такие соотношения при
2
=
k
, то есть
изучим соотношения вида
12
(2)(1)().
fnafnafn
+=++
(3)
Решение этих соотношений основано на следующих двух утвержде-
ниях:
1) Если )n(f
1
и )n(f
2
являются решениями рекуррентного соотноше-
ния (3), то при любых
A
и
B
последовательность )n(Bf)n(Af)n(f
21
+
=
также является решением этого соотношения. В самом деле, по условию имеем
)n(fa)n(fa)n(f
12111
12
+
+
=
+
и
21222
fnafnafn

Умножим эти равенства на
A
и
B
соответственно и сложим полу-
ченные тождества. Мы получим, что
12112
21
(2)(2)[(1)(1)]
[()()].
AfnBfnaAfnBfn
aAfnBfn
+++=++++
++
Это означает, что )n(Bf)n(Af)n(f
21
+
=
является решением нашего
соотношения.
2) Если число
1
r является корнем квадратного уравнения
21
2
arar += ,
то последовательность
,...r...,,r,r,
n 1
1
2
11
1
-
является решением рекуррентного соотношения
)n(fa)n(fa)n(f
21
12
+
+
=
+
.
Наряду с последовательностью
{
}
1
1
-n
r любая последовательность вида
mn
r)n(f
+
=
1
,
1,2,...
n
=
также является решением исследуемого соотношения.
Из утверждений 1) и 2) вытекает следующее правило решения ли-
нейных рекуррентных соотношений второго порядка с постоянными ко-
эффициентами: