Дискретная математика. Азарнова Т.В - 45 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Рекуррентные соотношения
45
§2. Линейные рекуррентные соотношения с постоянными коэффициен-
тами
Для решения рекуррентных соотношений общих правил не существует.
Однако существует весьма часто встречающийся класс соотношений, решае-
мых единообразным методом. Это – рекуррентные соотношения вида
)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
21
=
==
=
также является решением исследуемого соотношения.
Из утверждений 1) и 2) вытекает следующее правило решения линей-
ных рекуррентных соотношений второго порядка с постоянными коэффици-
ентами: 
                                             45
Рекуррентные соотношения
 §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 соответственно и сложим полу-
           ченные тождества. Мы получим, что
                      Af 1 ( n +2 ) +Bf 2 ( n +2 ) =a1 [ Af 1 ( n +1 ) +Bf 2 ( n +1 )] +
                                                                                        .
                      +a 2 [ Af 1 ( 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) вытекает следующее правило решения линей-
ных рекуррентных соотношений второго порядка с постоянными коэффици-
ентами:

Страницы