Дискретная математика. Азарнова Т.В - 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). 
                                         44
Рекуррентные соотношения
элементов последовательности можно задать совершенно произвольно —
между ними нет никаких соотношений. Но если первые k элементов заданы,
то все остальные элементы определяются совершенно однозначно — элемент
 f (k +1) выражается в силу рекуррентного соотношения через f (1),Κ , f (k ),
элемент f (k +2 ) — через f (2 ),Κ , f (k +1) и т.д.
        Будем говорить, что некоторая последовательность является решени-
ем данного рекуррентного соотношения, если при подстановке этой последо-
вательности соотношение тождественно выполняется. Например, последова-
тельность
                                          2 , 4 ,8,Κ , 2 n ,Κ
является одним из решений рекуррентного соотношения
                              f (n +2 ) =3 f (n +1) −2 f (n ).
        В самом деле, общий член этой последовательности имеет вид
 f (n ) =2 n . Значит, f (n +2 ) =2 n +2 , f (n +1) =2 n +1 . Но при любом n имеет ме-
сто тождество 2 n +2 =3 ⋅ 2 n +1 −2 ⋅ 2 n . Поэтому 2 n является решением указан-
ного соотношения.
      Решением рекуррентного соотношения k -го порядка называется об-
щим, если оно зависит от k произвольных постоянных C1 ,Κ , C k и путем
подбора этих постоянных можно получить любое решение данного соотно-
шения. Например, для соотношения
                      f (n +2 ) =5 f (n +1) −6 f (n )                         (1)
общим решением будет
                            f (n ) =C1 2 n +C 2 3 n .                         (2)
В самом деле, легко проверить, что последовательность обращает соотноше-
ние в тождество. Поэтому нам надо только показать, что любое решение на-
шего соотношения можно представить в виде (2). Но любое решение соот-
ношения (1) однозначно определяется значениями f (1) и f (2 ). Поэтому нам
надо доказать, что для любых чисел a и b найдутся такие значения C1 и C 2 ,
что
                                     2C1 +3C 2 =a
и
                                   2 2 C1 +3 2 C 2 =b .
Но легко видеть, что при любых значениях a и b система уравнений
                                    2C1 +3C 2 =a ,
                                    
                                    4C1 +9C 2 =b
имеет решение. Поэтому (2) действительно является общим решение соот-
ношения (1).

Страницы