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

UptoLike

Составители: 

55
k
элементов последовательности можно задать совершенно произвольно
между ними нет никаких соотношений. Но если первые
k
элементов зада-
ны, то все остальные элементы определяются совершенно однозначно
элемент
(
)
1
+
kf выражается в силу рекуррентного соотношения через
(
)
(
)
kf,,f
K
1 , элемент
(
)
2
+
kf через
(
)
(
)
12
+
kf,,f
K
и т. д.
Будем говорить, что некоторая последовательность является реше-
нием данного рекуррентного соотношения, если при подстановке этой по-
следовательности соотношение тождественно выполняется. Например, по-
следовательность
K
K
,,,,,
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 . Пусть
(
(
1=,2=
fafb
. Поэтому нам надо доказать, что для любых
чисел
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).