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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

с постоянными коэффициентами
Для решения рекуррентных соотношений общих правил не сущест -
вует . Однако существует весьма часто встречающийся класс соотношений,
решаемых единообразным методом. Это – рекуррентные соотношения ви-
да
)n(fa...)kn(fa)kn(fa)kn(f
k
+
+
−
+
+
−
+
=
+
21
21
,
где
k
a,...,a,a
21
- некоторые числа . Такие соотношения называются линей-
ными рекуррентными соотношениями с постоянными коэффициен-
тами.
Рассмотрим, как решаются такие соотношения при
2
=
k
, то есть
изучим соотношения вида
)n(fa)n(fa)n(f
21
12
+
+
=
+
. (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
+
+
=
+
и
)n(fa)n(fa)n(f
22212
12
+
+
=
+
.
Умножим эти равенства на
A
и
B
соответственно и сложим по -
лученные тождества . Мы получим, что
)]n(Bf)n(Af[a
)]n(Bf)n(Af[a)n(Bf)n(Af
++
+
+
+
+
=
+
+
+
12
21121
1122
.
Это означает , что )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
,
,...
,
n
2
1
=
также является решением исследуемого соотношения.
Из утверждений 1) и 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) +a 2 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 )] +
                                                                                     .
                     +a 2 [ 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) +a 2 f ( n ) .
                                                  { }
        Наряду с последовательностью r1n −1 любая последовательность
        вида
                            f ( n ) =r1n +m , n =1,2 ,...
        также является решением исследуемого соотношения.
     Из утверждений 1) и 2) вытекает следующее правило решения ли-
нейных рекуррентных соотношений второго порядка с постоянными ко-
эффициентами:

Страницы