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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Пусть дано рекуррентное соотношение
)n(fa)n(fa)n(f
21
12
+
+
=
+
.
Составим квадратное уравнение
21
2
arar += , (4)
которое называется характеристическим для данного соотношения.
Если это уравнение имеет два различных корня
1
r и
2
r , то общее реше-
ние рекуррентного соотношения имеет вид
2
22
1
11
−−
+=
nn
rCrC)n(f .
Действительно, по утверждению 2)
1
11
−
=
n
r)n(f и
1
22
−
=
n
r)n(f яв -
ляются решениями нашего соотношения. По утверждению 1) и
2
22
1
11
−−
+=
nn
rCrC)n(f
является его решением . Надо показать, что любое
решение соотношения можно записать в этом виде. Но любое решение ли-
нейного рекуррентного соотношения второго порядка определяется значе-
ниями )(f 1 и )(f 2 . Поэтому достаточно показать, что система уравнений
=+
=+
brCrC
aCC
2211
21
имеет решение при любых
a
и
b
. Этими решениями являются
.
rr
bar
C,
rr
arb
C
21
1
2
21
2
1
−
−
=
−
−
=
Случай, когда оба корня уравнения
21
2
arar += совпадают друг с другом,
мы разберем несколько позже. Рассмотрим пример.
При изучении чисел Фибоначчи мы пришли к рекуррентному соот -
ношению
)n(f)n(f)n(f 21
−
+
−
=
.
Для него характеристическое уравнение имеет вид
1
2
+
=
r
r
.
Корнями этого квадратного уравнения являются числа
.r,r
2
51
2
51
11
−
=
+
=
Поэтому общее решение соотношения Фибоначчи имеет вид
nn
CC)n(f
−
+
+
=
2
51
2
51
21
.
3.3 Случай равных корней характеристического уравнения
Остановимся теперь на случае, когда оба корня характеристического 
           Пусть дано рекуррентное соотношение
                               f ( n +2 ) =a1 f ( n +1) +a 2 f ( n ) .
Составим квадратное уравнение
                                        r 2 =a1r +a2 ,                             (4)
которое называется характеристическим для данного соотношения.
Если это уравнение имеет два различных корня r1 и r2 , то общее реше-
ние рекуррентного соотношения имеет вид
                       f ( n ) =C1 r1n −1 +C 2 r2n −2 .
         Действительно, по утверждению 2) f 1( n ) =r1n −1 и f 2 ( n ) =r2n −1 яв-
ляются решениями нашего соотношения. По утверждению 1) и
 f ( n ) =C1 r1n −1 +C 2 r2n −2 является его решением. Надо показать, что любое
решение соотношения можно записать в этом виде. Но любое решение ли-
нейного рекуррентного соотношения второго порядка определяется значе-
ниями f ( 1) и f ( 2 ) . Поэтому достаточно показать, что система уравнений
                                      � C 1 +C 2 =a
                                       �
                                         � C 1 r1 +C 2 r2 =b
имеет решение при любых a и b . Этими решениями являются
                                     b −ar2                ar −b
                                C1 =              , C2 = 1        .
                                     r1 −r2                r1 −r2
Случай, когда оба корня уравнения r 2 =a1r +a2 совпадают друг с другом,
мы разберем несколько позже. Рассмотрим пример.
     При изучении чисел Фибоначчи мы пришли к рекуррентному соот-
ношению
                        f ( n ) = f ( n −1) + f ( n −2 ) .
Для него характеристическое уравнение имеет вид
                                    r 2 =r +1.
Корнями этого квадратного уравнения являются числа
                               1+ 5            1− 5
                          r1 =          , r1 =        .
                                  2               2
Поэтому общее решение соотношения Фибоначчи имеет вид
                                                       n                     n
                                      � 1+ 5 �                     � 1− 5 �
                      f ( n ) =C 1 ��          �
                                                 �         +C 2 ��          � .
                                                                             �
                                       �  2        �                �  2       �


      3.3 Случай равных корней характеристического уравнения

      Остановимся теперь на случае, когда оба корня характеристического

Страницы