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

UptoLike

Рекуррентные соотношения
46
Пусть дано рекуррент ное соотношение
)n(fa)n(fa)n(f
21
12
+
++
++
++
+=
==
=+
++
+
.
Составим квадратное уравнение
21
2
arar
+
++
+=
==
=
,
которое называется характеристическим для данного соотношения. Ес-
ли эт о уравнение имеет два различных корня
1
r
и
2
r
, то общее решение
рекуррентного соотношения имеет вид
2
22
1
11
+=
nn
rCrC)n(f
.
Действительно, по утверждению 2)
1
11
=
==
=
n
r)n(f
и
1
22
=
==
=
n
r)n(f
явля-
ются решениями нашего соотношения. По утверждению 1) и
2
22
1
11
+=
nn
rCrC)n(f
является его решением. Надо показать, что любое
решение соотношения можно записать в этом виде. Но любое решение ли-
нейного рекуррентного соотношения второго порядка определяется значе-
ниями
)(f
1
и
)(f
2
. Поэтому достаточно показать, что система уравнений
=+
=+
brCrC
aCC
2211
21
имеет решение при любых
a
и
b
. Этими решениями являются
.
rr
bar
C,
rr
arb
C
21
1
2
21
2
1
=
==
=
=
==
=
Случай, когда оба корня уравнения
21
2
arar
+
++
+=
==
=
совпадают друг с другом,
мы разберем несколько позже. Рассмотрим пример.
При изучении чисел Фибоначчи мы пришли к рекуррентному соотно-
шению
)n(f)n(f)n(f
21
+
++
+
=
==
=
.
Для него характеристическое уравнение имеет вид
1
2
+
++
+=
==
= rr
.
Корнями этого квадратного уравнения являются числа
.r,r
2
51
2
51
11
=
==
=
+
++
+
=
==
=
Поэтому общее решение соотношения Фибоначчи имеет вид
nn
CC)n(f
+
++
+
+
++
+
=
==
=
2
51
2
51
21
.