Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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 Линейные рекуррентные соотношения 
        Если задано рекуррентное соотношение k -го порядка, то ему удов-
летворяет бесконечно много последовательностей. Дело в том, что первые
k элементов последовательности можно задать совершенно произвольно
— между ними нет никаких соотношений. Но если первые 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 ). Пусть
 f (1) =a, f (2) =b . Поэтому нам надо доказать, что для любых чисел 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).

                3.2 Линейные рекуррентные соотношения

Страницы