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

UptoLike

с постоянными коэффициентами
Для решения рекуррентных соотношений общих правил не сущест -
вует . Однако существует весьма часто встречающийся класс соотношений,
решаемых единообразным методом. Это рекуррентные соотношения ви-
да
)n(fa...)kn(fa)kn(fa)kn(f
k
+
+
+
+
+
=
+
21
21
,
где
k
a,...,a,a
21
- некоторые числа . Такие соотношения называются линей-
ными рекуррентными соотношениями с постоянными коэффициен-
тами.
Рассмотрим, как решаются такие соотношения при
2
=
k
, то есть
изучим соотношения вида
)n(fa)n(fa)n(f
21
12
+
+
=
+
. (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
+
+
=
+
и
)n(fa)n(fa)n(f
22212
12
+
+
=
+
.
Умножим эти равенства на
A
и
B
соответственно и сложим по -
лученные тождества . Мы получим, что
)]n(Bf)n(Af[a
)]n(Bf)n(Af[a)n(Bf)n(Af
++
+
+
+
+
=
+
+
+
12
21121
1122
.
Это означает , что )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
,
,...
,
n
2
1
=
также является решением исследуемого соотношения.
Из утверждений 1) и 2) вытекает следующее правило решения ли-
нейных рекуррентных соотношений второго порядка с постоянными ко-
эффициентами: