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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

59
Если же, например,
s
rrr
=
=
=
K
21
, то этому корню соответствуют
решения
(
)
(
)
(
)
(
)
1
1
11
1
2
3
1
12
1
11
-----
====
ns
s
nnn
rnnf,,rnnf,nrnf,rnf
K
рассматриваемого рекуррентного соотношения. В общем решении этому
корню соответствует часть
[
]
12
321
1
1
--
++++
s
s
n
nCnCnCCr
K
.
Составляя такие выражения для всех корней и складывая их, получа-
ем общее решение.
Например, решим рекуррентное соотношение
(
)
(
)
(
)
(
)
(
)
nfnfnfnfnf 81426354
+
+
-
+
-
+
=
+
.
Характеристическое уравнение имеет здесь вид
0
8
4
6
5
234
=-++-
r
r
r
r
.
Решая его, получаем корни
.r,r,r,r 1222
4321
-
=
=
=
=
Значит, общее решение нашего соотношения имеет следующий вид:
(
)
[
]
(
)
1
4
2
321
1
12
-
-
-+++=
n
n
CnCnCCnf .
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Написать первые пять членов решения рекуррентного соотноше-
ния
(
)
(
)
(
)
nfnfnf 3122
-
+
=
+
, удовлетворяющего заданным начальным
условиям:
1)
(
)
()
;
21
f
f
=
ì
ï
í
=
ï
î
2)
(
)
()
11
;
21
f
f
=-
ì
ï
í
=
ï
î
3)
(
)
()
13
;
20
f
f
=
ì
ï
í
=
ï
î
4)
(
)
()
12
;
21
f
f
=
ì
ï
í
=
ï
î
5)
(
)
()
12
.
28
f
f
=
ì
ï
í
=
ï
î
2. Проверить, являются ли данные функции решениями данных ре-
куррентных соотношений:
1)
(
)
(
)
(
)
() () ()
.n,nn,n
;nfnfnf
n
31225
122
321
=+=×=
-
+
=
+
jjj
2)
(
)
(
)
(
)
() () ()
71352
3142
321
=-×==
-
+
=
+
n,n,nn
;nfnfnf
n
jjj
3. Найти общее решение рекуррентных соотношений:
1)
(2)7(1)12()0;
fnfnfn
+-++=
2) 010132
=
-
+
+
+
)n(f)n(f)n(f ;
3) 013142
=
+
+
-
+
)n(f)n(f)n(f ; 
     Если же, например, r1 � r2 � � � rs , то этому корню соответствуют
решения
        f 1 �n � � r1n �1 , f 2 �n � � nr1n �1 , f 3 �n � � n 2 r1n �1 ,� , f s �n � � n s �1 r1n �1
рассматриваемого рекуррентного соотношения. В общем решении этому
корню соответствует часть
                                  �
                          r1n �1 C1 � C 2 n � C 3 n 2 � � � C s n s �1 .�
     Составляя такие выражения для всех корней и складывая их, получа-
ем общее решение.
     Например, решим рекуррентное соотношение
                   f �n � 4 � � 5 f �n � 3� � 6 f �n � 2 � � 4 f �n � 1� � 8 f �n � .
     Характеристическое уравнение имеет здесь вид
                                 r 4 � 5r 3 � 6r 2 � 4r � 8 � 0 .
     Решая его, получаем корни
                                 r1 � 2 , r2 � 2 , r3 � 2 , r4 � �1.
     Значит, общее решение нашего соотношения имеет следующий вид:
                                            �                       �
                            f �n � � 2 n �1 C1 � C 2 n � C 3 n 2 � C 4 �� 1� .
                                                                                     n �1




                                ЗАДАЧИ И УПРАЖНЕНИЯ

       1. Написать первые пять членов решения рекуррентного соотноше-
ния f �n � 2 � � 2 f �n � 1� � 3 f �n � , удовлетворяющего заданным начальным
условиям:
   �� f �1� � 0       �� f �1� � �1        �� f �1� � 3        �� f �1� � 2       �� f �1� � 2
1) �             ; 2) �              ; 3) �               ; 4) �             ; 5) �            .
    � f � 2 � � 1      � f � 2 � � 1        � f � 2 � � 0       � f � 2 � � 1      � f � 2� � 8

     2. Проверить, являются ли данные функции решениями данных ре-
куррентных соотношений:

            f �n � 2 � � 2 f �n � 1� � f �n �;
       1)
            � 1 �n � � 5 � 2 n , � 2 �n � � 2n � 1, � 3 �n � � 3.

            f �n � 2 � � 4 f �n � 1� � 3 f �n �;
       2)
          � 1 �n � � 2n , � 2 �n � � 5 � 3 n � 1, � 3 �n � � 7
       3. Найти общее решение рекуррентных соотношений:
       1) f (n � 2) � 7 f (n � 1) � 12 f (n) � 0;
       2) f ( n � 2 ) � 3 f ( n � 1) � 10 f ( n ) � 0 ;
       3) f ( n � 2 ) � 4 f ( n � 1) � 13 f ( n ) � 0 ;

                                                    59

Страницы