Дискретная математика. Азарнова Т.В - 45 стр.

UptoLike

Рекуррентные соотношения
45
§2. Линейные рекуррентные соотношения с постоянными коэффициен-
тами
Для решения рекуррентных соотношений общих правил не существует.
Однако существует весьма часто встречающийся класс соотношений, решае-
мых единообразным методом. Эторекуррентные соотношения вида
)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
21
=
==
=
также является решением исследуемого соотношения.
Из утверждений 1) и 2) вытекает следующее правило решения линей-
ных рекуррентных соотношений второго порядка с постоянными коэффици-
ентами: