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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

56
3.2 Линейные рекуррентные соотношения
с постоянными коэффициентами
Для решения рекуррентных соотношений общих правил не существу-
ет. Однако существует весьма часто встречающийся класс соотношений,
решаемых единообразным методом. Это – рекуррентные соотношения вида
)n(fa...)kn(fa)kn(fa)kn(f
k
+
+
-
+
+
-
+
=
+
21
21
,
где
k
a,...,a,a
21
– некоторые числа. Такие соотношения называются ли-
нейными рекуррентными соотношениями с постоянными коэффици-
ентами.
Рассмотрим, как решаются такие соотношения при
2
=
k
, то есть
изучим соотношения вида
12
(2)(1)().
fnafnafn
+=++
(3)
Решение этих соотношений основано на следующих двух утвержде-
ниях:
1) Если )n(f
1
и )n(f
2
являются решениями рекуррентного соотноше-
ния (3), то при любых
A
и
B
последовательность )n(Bf)n(Af)n(f
21
+
=
также является решением этого соотношения. В самом деле, по условию имеем
)n(fa)n(fa)n(f
12111
12
+
+
=
+
и
21222
fnafnafn

Умножим эти равенства на
A
и
B
соответственно и сложим полу-
ченные тождества. Мы получим, что
12112
21
(2)(2)[(1)(1)]
[()()].
AfnBfnaAfnBfn
aAfnBfn
+++=++++
++
Это означает, что )n(Bf)n(Af)n(f
21
+
=
является решением нашего
соотношения.
2) Если число
1
r является корнем квадратного уравнения
21
2
arar += ,
то последовательность
,...r...,,r,r,
n 1
1
2
11
1
-
является решением рекуррентного соотношения
)n(fa)n(fa)n(f
21
12
+
+
=
+
.
Наряду с последовательностью
{
}
1
1
-n
r любая последовательность вида
mn
r)n(f
+
=
1
,
1,2,...
n
=
также является решением исследуемого соотношения.
Из утверждений 1) и 2) вытекает следующее правило решения ли-
нейных рекуррентных соотношений второго порядка с постоянными ко-
эффициентами: 
                  3.2 Линейные рекуррентные соотношения
                       с постоянными коэффициентами

      Для решения рекуррентных соотношений общих правил не существу-
ет. Однако существует весьма часто встречающийся класс соотношений,
решаемых единообразным методом. Это – рекуррентные соотношения вида
             f ( n � k ) � a1 f ( n � k � 1) � a2 f ( n � k � 2 ) � ... � a k f ( n ) ,
где a1 , a2 ,..., a k – некоторые числа. Такие соотношения называются ли-
нейными рекуррентными соотношениями с постоянными коэффици-
ентами.
      Рассмотрим, как решаются такие соотношения при k � 2 , то есть
изучим соотношения вида
                               f (n � 2) � a1 f (n � 1) � a2 f (n).                     (3)
      Решение этих соотношений основано на следующих двух утвержде-
ниях:
      1) Если f 1( n ) и f 2 ( n ) являются решениями рекуррентного соотноше-
ния (3), то при любых A и B последовательность f ( n ) � Af 1( n ) � Bf 2 ( n )
также является решением этого соотношения. В самом деле, по условию имеем
                                  f 1( n � 2 ) � a1 f 1( n � 1) � a2 f 1( n )
и
                                   f 2 (n  2)  a1 f 2 (n  1)  a2 f 2 (n).
      Умножим эти равенства на A и B соответственно и сложим полу-
ченные тождества. Мы получим, что
                       Af1 (n � 2) � Bf 2 (n � 2) � a1[ Af1 (n � 1) � Bf 2 (n � 1)] �
               � a2 [ Af1 (n) � Bf (n)].
     Это означает, что f ( n ) � Af 1( n ) � Bf 2 ( n ) является решением нашего
соотношения.
     2) Если число r1 является корнем квадратного уравнения
                                         r 2 � a1r � a2 ,
то последовательность
                                1, r1 , r12 , ..., r1n �1 ,...
является решением рекуррентного соотношения
                       f ( n � 2 ) � a1 f ( n � 1) � a2 f ( n ) .
                                            � �
       Наряду с последовательностью r1n �1 любая последовательность вида
                        f ( n ) � r1n � m , n � 1, 2, ...
также является решением исследуемого соотношения.
     Из утверждений 1) и 2) вытекает следующее правило решения ли-
нейных рекуррентных соотношений второго порядка с постоянными ко-
эффициентами:

                                            56

Страницы