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

UptoLike

Рекуррентные соотношения
44
элементов последовательности можно задать совершенно произвольно
между ними нет никаких соотношений. Но если первые
k
элементов заданы,
то все остальные элементы определяются совершенно однозначноэлемент
()
1
+
kf
выражается в силу рекуррентного соотношения через
() ( )
kf,,f
Κ
1
,
элемент
()
2
+
kf
через
() ( )
12
+
kf,,f
Κ
и т.д.
Будем говорить, что некоторая последовательность является
решени-
ем
данного рекуррентного соотношения, если при подстановке этой последо-
вательности соотношение тождественно выполняется. Например, последова-
тельность
ΚΚ
,,,,,
n
2842
является одним из решений рекуррентного соотношения
()()()
.nfnfnf
2132
+=+
В самом деле, общий член этой последовательности имеет вид
()
n
nf
2
=
. Значит,
() ()
.nf,nf
nn
12
2122
++
=+=+
Но при любом
n
имеет ме-
сто тождество
.
nnn
22232
12
=
++
Поэтому
n
2 является решением указан-
ного соотношения.
Решением рекуррентного соотношения
k
-го порядка называется об-
щим, если оно зависит от
k
произвольных постоянных
k
C,,C
Κ
1
и путем
подбора этих постоянных можно получить любое решение данного соотно-
шения. Например, для соотношения
()()()
nfnfnf
6152
+=+
(1)
общим решением будет
()
nn
CCnf
32
21
+=
. (2)
В самом деле, легко проверить, что последовательность обращает соотноше-
ние в тождество. Поэтому нам надо только показать, что любое решение на-
шего соотношения можно представить в виде (2). Но любое решение соот-
ношения (1) однозначно определяется значениями
()
1
f
и
()
2
f
. Поэтому нам
надо доказать, что для любых чисел
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).