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

UptoLike

Если задано рекуррентное соотношение
k
-го порядка , то ему удов-
летворяет бесконечно много последовательностей. Дело в том, что первые
k
элементов последовательности можно задать совершенно произвольно
между ними нет никаких соотношений. Но если первые
k
элементов
заданы, то все остальные элементы определяются совершенно однозначно
элемент
(
)
1
+
kf выражается в силу рекуррентного соотношения через
(
)
(
)
kf,,f K1 , элемент
(
)
2
+
kf через
(
)
(
)
12
+
kf,,f K и т . д .
Будем говорить, что некоторая последовательность является реше-
нием данного рекуррентного соотношения, если при подстановке этой по -
следовательности соотношение тождественно выполняется. Например, по -
следовательность
KK ,,,,,
n
2842
является одним из решений рекуррентного соотношения
(
)
(
)
(
)
.nfnfnf 2132
+
=
+
В самом деле, общий член этой последовательности имеет вид
(
)
n
nf 2= . Значит,
(
)
(
)
.nf,nf
nn 12
2122
++
=+=+ Но при любом
n
имеет
место тождество
.
nnn
2
2
2
3
2
12
=
++
Поэтому
n
2
является решением
указанного соотношения.
Решение рекуррентного соотношения
k
-го порядка называется об-
щим, если оно зависит от
k
произвольных постоянных
k
C,,C K
1
и путем
подбора этих постоянных можно получить любое решение данного соот -
ношения. Например, для соотношения
(
)
(
)
(
)
nfnfnf 6152
+
=
+
(1)
общим решением будет
(
)
nn
CCnf 32
21
+=
. (2)
В самом деле, легко проверить, что последовательность обращает соотно-
шение в тождество. Поэтому нам надо только показать, что любое решение
нашего соотношения можно представить в виде (2). Но любое решение со -
отношения (1) однозначно определяется значениями
(
)
1f и
(
)
2f . Пусть
(
)
(
)
bfaf
=
=
2,1
. Поэтому нам надо доказать, что для любых чисел
a
и
b
найдутся такие значения
1
C и
2
C , что
aCC
=
+
21
32
и
bCC =+
2
2
1
2
32 .
Но легко видеть, что при любых значениях
a
и
b
система уравнений
=+
=+
bCC
,aCC
21
21
94
32
имеет решение. Поэтому (2) действительно является общим решение соот -
ношения (1).
3.2 Линейные рекуррентные соотношения